[DP] 쉬운 계단 수 (백준 10844번)

 

문제 이름은 쉬운 계단 수인데, 사실 쉽지 않다, 저기 정답 비율만 봐도 28.216%지 않은가.

물론 DP에 능숙해졌다면 몇 번의 시행 착오만 겪어도 풀 수 있는 문제긴 하겠지만.

자세한 설명은 코드를 먼저 보여준 다음에 이어 나가는 게 좋을 거 같다, 주석을 달아 놨으니.

 

#include <iostream>
using namespace std;
 
long long int dp[101][10];
long long int mod = 1000000000;
int n;
 
int main(void)
{
    cin >> n;
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1;
    
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if (j == 0) dp[i][j] = dp[i - 1][1];
            else if (j == 9) dp[i][j] = dp[i - 1][8];
            else
            {
                dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1]) % mod;
            }
        }
    }
    long long int sum = 0;
    for (int i = 0; i <= 9; i++)
        sum += dp[n][i];
 
    cout << sum % mod;
}
 
/*
1
2
3
4
5
6
7
8
9
 
1 10 12
2 21 23
3 32 34
4 43 45
5 54 56
6 65 67
7 76 78
8 87 89
9 98
 
모든 수는 다른 수 2개를 계단수로 가지지만,
그 중에서 0은 계단수를 가지지 못하고, 9는 계단수를 1개만 가진다.
그래서 dp[1] = 9이고
dp[2]는 0과 9를 합쳐 1개, 1 ~ 8을 합쳐 16개, 총 17개가 된다.
dp[2]의 계단수들은(0 1개, 1 1개, 9 1개 나머지 2개씩을 가진다.
 
고로 0과 9를 따로 관리해줘야 한다.
 
1에서 0이 1개 발생하고,
8에서 9가 1개 발생한다.
*/    
 
// 아, 이게 오버플로우가 발생하는구나.

 

DP를 똑같이 해주되, 예외 처리를 해주어야 한다.

 

DP가 다 그렇지만, 구성 자체는 너무 simple하지만 그 발상을 떠올리는 게 힘들다.

이전 항에서 다음 항으로 넘어갈 때 일어나는 차이점, 또는 공식, 조건식, 그런 게 떠올리기가 힘들다.

다른 문제는 일단 쳐보면서 생각이라도 할 수 있지만,

DP 문제는 막히면 그냥 멍하니 모니터만 쳐다보면서, 이걸 어떻게 해야 하지 고민해야 하는 문제다.

그래서 나는 집중이 되지 않는 곳에서는 DP 문제를 풀지 않는다. 각설하고,

 

밑에 주석을 다시 정리하자면

계단 수는 서로 붙어 있는 모든 자리수가 1의 차이를 가지는 수를 말한다고 했다.

그러면 한 자리 수 1~9 까지가 있을 때, 모든 수들은 자신보다 1 작거나 1 큰 수를 좌측에 붙임으로써 성립된다.

반대로 1 작거나 1 큰 수를 우측에 붙이는 것은, 중복이 발생할 테니 고려할 필요 없다.

여기서 문제가, 0과 9이다.

만약 기준이 되는 index에 대한 값이 0이라면 좌측에 붙일 수 있는 것은 -1이 불가능하니 1밖에 없고

만약 기준이 되는 index에 대한 값이 9라면 좌측에 붙일 수 있는 것은 10이 불가능하니 8밖에 없다.

 

고로

 

 for (int i = 2; i <= n; i++)

    {

        for (int j = 0; j <= 9; j++)

        {

            if (j == 0) dp[i][j] = dp[i - 1][1];

            else if (j == 9) dp[i][j] = dp[i - 1][8];

            else

            {

                dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1]) % mod;

            }

        }

    }

의 꼴이 성립한다.

 

바깥쪽 for문에 대해서는 int i = 2부터 시작하는 이유는, i = 1인 경우는 미리 입력이 다 되기 때문이다.

(여기서 i는 자릿수를 의미한다, int i = 3이라면, 세 자리수를 의미한다.)

안쪽 for문은, 다시 가장 우측에 붙는 수가 0부터 9인 경우를 구하기 위해서인데,

예컨대 i == 3 이고 j == 0인 상황이 있다면, 세 자리 수 중에서 우측 끝이 0인 경우를 의미한다.

당연 이것은 i == 2 이면서 j == 1였던 경우만이 성립된다.

 

i == 3 이고 j == 9 인 경우는 당연 j == 2 이고 j == 8인 경우와 같을 수밖에 없다.

 

그 외 j가 2부터 8인 수들에 대해서는 i는 1보다 작고 (자리수가 1개 작고)

j는 1 작거나 1 큰 수들의 개수를 모두 더함으로써 구할 수 있으니 다음과 같이 된다.