문제#

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력#

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력#

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이#

이 문제를 봤을 때 계단 수를 찾는 과정 자체가 탐색을 해야하고 그 과정이 메모이제이션을 활용할 것 같아 DP를 활용해야겠다고 생각했습니다.

dp 배열은 2차원 배열로 정의했고 행은 자리수, 열은 0-9의 숫자로 정의했습니다.

그에 따른 점화식은 i행 j열일때 i-1행 j-1,j+1열의 값을 가져와 더하는 것으로 정의했습니다.

dp의 관련된 요소는 여기까지고 이 문제의 본질은 계산 과정에서 숫자가 매우 커진다는 것인데 따라서 출력도 1’000’000’000으로 나눈 값으로 출력하라고 나와있습니다.

이 문제를 위해서는 계산 과정 중간중간의 모듈러 연산을 활용해야했습니다.

모듈러 연산 중 덧셈에 관한 것을 활용했는데 그 내용은 다음과 같습니다.

$(a + b) \mod n = \{(a \mod n )+ (b \mod n)\} \mod n$

코드#

#include <iostream>

using namespace std;

int N;

unsigned long long dp[100][10];

int main()
{
    cin >> N;

    for (int i = 1; i < 10; ++i)
    {
        dp[0][i] = 1;
    }

    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if (j != 0 && j != 9)
                dp[i][j] = (dp[i - 1][j - 1] % 1'000'000'000 +
                            dp[i - 1][j + 1] % 1'000'000'000) %
                           1'000'000'000;
            else if (j == 0)
                dp[i][j] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1];
        }
    }

    unsigned long long result = 0;

    for (int i = 0; i < 10; ++i)
    {
        result = (result + dp[N - 1][i] % 1'000'000'000) % 1'000'000'000;
    }

    cout << result;
}