BOJ 10844 쉬운 계단 수

boj 10844 쉬운 계단 수

길이가 N인 계단 수의 경우의 수를 어떻게 나눌 수 있을까. 맨 끝의 숫자가 0~9 중 하나인 것은 자명하다. 맨 끝의 숫자가 0일 경우를 생각해보면, 계단 수이므로 0 앞의 수는 1만 가능하다. 즉, 길이가 N-1이고 끝이 1인 계단 수만이 0 앞에 올 수 있다는 의미이다. 맨 끝의 숫자가 9인 경우는, 9 앞의 수로 8만 올 수 있다. 남은 경우인 맨 끝의 숫자가 1부터 8 사이의 경우는, 각 수에서 1씩 더하거나 뺀 수들이 앞에 올 수 있다. 이 내용을 점화식으로 나타내보자. 테이블로 D[i][j]는 길이가 i이고 맨 끝 수가 j인 계단 수의 갯수라고 한다.

j가 0 일 때, D[i][j] = D[i-1][j+1]
j가 9 일 때, D[i][j] = D[i-1][j-1]
j가 1-8 사이일 때, D[i][j] = D[i-1][j-1] + D[i-1][j+1]

점화식을 바탕으로 코드를 구현했다.

#include <iostream>
using namespace std;

int n;
int D[105][13];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= 9; i++) D[1][i] = 1;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if (j == 0) D[i][j] = D[i - 1][j + 1];
            else if (j == 9) D[i][j] = D[i - 1][j - 1];
            else D[i][j] = (D[i - 1][j + 1] + D[i - 1][j - 1]) % 1000000000;
        }
    }

    long long ans = 0;

    for (int i = 0; i <= 9; i++)
        ans += D[n][i];

    cout << ans % 1000000000;
}