[알고리즘 문제] 백준10844 - 쉬운 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

처음 문제를 읽고 이해가 잘 안되어서 다른분의 풀이는 참조하였다. dp로 풀어야 하는데, 문제가 이해 안가다 보니 어떻게 접근해야 하는지도 몰랐다. 어떻게 문제를 이해하고 풀고 다시 읽어보니...처음에 너무 문제를 어렵게 생각하지 않았나 싶다.

 

계단수란 어떤 숫자에서 인접한 숫자의 차이가1 인 수를 의미한다. 예를 들어 1232345는 각 위치의 숫자와 인접한 숫자의 차이가 1이기 때문에 계단 수 이지만, 1245인 경우 2와4는 차이가 2가 나기 때문에 계단수가 아니다.

 

또 문제에서 길이란, 숫자의 길이를 의미한다. 123의 길이는 3, 1234의 길이는 4 이런식...

 

문제는 길이가 N인 계단의 수가 몇개나 있는지를 구하는 문제이다. 길이가 2인 계단의 수는  1,0, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98으로 총 17개가 된다. 하지만 이것을 하나하나 다 구해야 할까..?

 

이렇게 생각해보자. [a,b] = n 에서, a는 숫자의 길이, b는 n의 마지막 숫자라고 표현해보자. 

 

[2,3] = 23 (길이가 2이고, 마지막 숫자가3)

[2,4] = 34 (길이가 2이고, 마지막 숫자가4)

[2,5] = 45 (길이가 2이고, 마지막 숫자가5)

 

여기서 중요한 점은 각각의 마지막 숫자 다음에는 오는 숫자는 b+1, b-1인 숫자가 올 수 있다. 즉 23다음에는 232, 234가 올 수 있다는 의미이다. 

 

자 그럼 몇단계 더 나아가보자

[3,4]는 길이가 3이고 마지막 숫자가 4인 경우이다. 그러면 234, 454가 올 수 있다. 그 외의 숫자는 조건을 만족하지 못한다.

 

근데 234, 454라는 숫자를 잘 살펴보면, 23+4, 45+4가 된다. 여기서 각각 23은 [2,3], 45는 [2,5]가 된다. 이 말은 [3,4]는 [2,3]와 [2,5]로 표현할 수 있다는 것이다. 

 

그렇다면 이를 2차원 배열 arr[a][b]로 표현해보자. 위와 다른 점은, arr[a][b]에 저장되는 값은 실제 숫자가 아니라 길이가 a이고 마지막 숫자가 b인 숫자의 "개수"를 저장한다.

 

위에서 [3,4]는 [2,3]와 [2,5]로 표현할 수 있다고 하였다. 이를 풀어 설명하면 길이가 3이고 마지막 숫자가 4인 경우는 234([2,3] + 4)와 454([4,5] + 4)가 된다. 이를 일반화 하면 arr[a][b] = arr[a-1][b-1] + arr[a-1][b+1]가 된다. 다시 말하지만, 각각의 배열에는 a,b를 만족하는 숫자의 개수가 저장되어 있다. 

 

하지만 예외의 경우도 존재하는데, 0과 9인 경우이다. 0인 경우는 왼쪽에 해당하는 값이 없고, 9인 경우는 오른쪽에 해당하는 값이 없기 때문에 예외처리를 해준다. 또한 문제에서 값이 커지는 경우를 대비해 100000000으로 나눈 나머지를 저장하라고 했으니 이 부분도 처리해준다.

 

#include <iostream>

using namespace std;

int dp[101][101];

int main()
{
    int n;
    cin >> n;

    // 길이가 1이고, 끝이 i인 숫자는 하나밖에 없다(1,2,3,4,5,6,7,8,9)
    for (int i = 1; i <= 9; i++)
    {
        dp[1][i] = 1;
    }

    int mod = 1000000000;
    // i : 자리수
    // j : i자리수의 마지막 숫자

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

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

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

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

    int result = 0;

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