# 10844. 쉬운 계단 수

관련 알고리즘 : DP

 

문제 링크 : https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

문제 풀이

n자리 숫자 중 계단수(각 자릿수마다 있는 수의 차이가 1인 수)의 개수를 구하는 문제이다.

'일의 자리 숫자가 무엇인가' 와 'n(자리수)'를 기준으로 dp 식을 세우면 문제를 해결할 수 있다.

 

n=2인 경우를 예를 들어 생각해보자.

일의 자리	십의 자리	개수
0	1	1
1	2	1
2	1, 3	2
3	2, 4	2
4	3, 5	2
5	4, 6	2
6	5, 7	2
7	6, 8	2
8	7, 9	2
9	8	1

십의 자리 숫자가 일의 자리 숫자가 무엇이느냐에 따라 영향을 받는 것을 알 수 있다.

0, 1, 9를 제외한 나머지 숫자들은 모두 (해당숫자-1), (해당숫자+1) 이렇게 2가지씩 경우가 존재한다.

 

그렇다면, 위를 토대로 n=3일 경우를 생각해보자.

일의 자리	백의 자리 + 십의 자리 + (일의 자리)
0	n=2일때 중 일의 자리가 1인 수 + (일의 자리 0)
1	n=2일때 중 일의 자리가 0 / 2인 수 + (일의 자리 1)
2	n=2일때 중 일의 자리가 1 / 3인 수 + (일의 자리 2)
3	n=2일때 중 일의 자리가 2 / 4인 수 + (일의 자리 3)
4	n=2일때 중 일의 자리가 3 / 5인 수 + (일의 자리 4)
5	n=2일때 중 일의 자리가 4 / 6인 수 + (일의 자리 5)
6	n=2일때 중 일의 자리가 5 / 7인 수 + (일의 자리 6)
7	n=2일때 중 일의 자리가 6 / 8인 수 + (일의 자리 7)
8	n=2일때 중 일의 자리가 7 / 9인 수 + (일의 자리 8)
9	n=2일때 중 일의 자리가 8인 수 + (일의 자리 9)

즉, n자리수의 계단수 개수는 일의 자리와 (n-1)자리수의 계단수 개수에 영향을 받는 것을 알 수 있다.

따라서, 점화식을 세우면 다음과 같다.

 

d[i][j] : i의 자리수를 갖는, 일의 자리가 j인 계단수의 개수

j = 0일 시, d[i][0] = d[i-1][1]

j = 1~8일 시, d[i][j] = d[i-1][j-1] + d[i-1][j+1]

j = 9일 시, d[i][9] = d[i-1][8]

 

---

※ 주의할 점(mod 연산 시)

처음에는 d[n][0~9]값들을 모두 구한 후, 이를 다 합쳐 res 변수에 저장하고

최종적으로 결과를 출력할 때 mod값( 1,000,000,000 ) 으로 나눠주었다.

 

그러나 백준 저지에서 계속 틀렸다고 나왔다. 내 ide에서는 결과값이 멀쩡하게 잘 나오는데 말이다!

 

검색해보니, 모든 연산을 마치고 마지막으로 mod 값으로 나눠서 한큐에 해결하고자 하면

자료형의 한계 범위를 넘어가서 오버플로우가 발생할 수 있다고 한다.

 

따라서 이와 같은 문제를 해결하기 위해서는 '모듈러 연산의 분배법칙'을 따른다.

 

📍모듈러 연산의 분배법칙

1. (a+b) mod p = (a mod p + b mod p) mod p   
2. (a×b) mod p = (a mod p × b mod p) mod p   
3. (a−b) mod p = (a mod p − b mod p) mod p

즉, 중간중간 모듈러 연산을 해 줘야 이후 오버플로우 발생을 예방할 수 있다.

 

참고 : https://velog.io/@chnh506/%EB%AA%A8%EB%93%88%EB%9F%ACModular-%EC%97%B0%EC%82%B0%EC%9D%98-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99-%EC%A0%95%EB%A6%AC

---

 

C++ 코드

#include <iostream>

using namespace std;
#define mod 1000000000

int n;
int d[101][10]; // d[i][j]일 때, i자리 숫자 중 일의자리 수가 j인 경우의 수
int res = 0;

void dp()
{
    for(int i=1; i<10; i++)
        d[1][i] = 1;
        
    for(int i=2; i<=n; i++)
    {
        for(int j=0; j<10; j++)
        {
            if(j==0)
                d[i][0] = d[i-1][j+1];
            else if(j==9)
                d[i][9] = d[i-1][j-1];
            else
                d[i][j] = d[i-1][j-1] + d[i-1][j+1];

            d[i][j] %= mod;
        }
    }
}

int main()
{
    cin >> n;

    dp();    
    for(int i=0; i<10; i++)
    {
        res = (res+d[n][i]) % mod;
    }
    
    cout << res;
    return 0;
}