10844번: 쉬운 계단 수

10844번: 쉬운 계단 수

풀이

D[i][j]는 길이가 i이고 끝자리 숫자가 j인 계단 수
n=1일때의 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9이고 n=2 일때의 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, ··· 등이 있다.
D[2][2]일 경우를 한 번 보자. 12, 32가 있는데 첫 자리 수는 끝자리 수인 2에서 ±1이다.
그래서 관계식이 D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9)D[i][j] = D[i - 1][j + 1] + D[i - 1][j - 1](j \ne 0|j \ne 9)D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9) 이렇게 나온다.
j = 0일땐 D[i][j] = D[i - 1][j + 1]이고 j = 9일땐 D[i][j] = D[i - 1][j - 1]이다.

룰루랄라~~

코드

#include <cstdio>

int n, D[101][10] = {
           {},
           {0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};
const int div = 1000000000;

int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            if (j == 9)
                D[i][j] = (D[i - 1][j - 1] % div);
            else if (j == 0)
                D[i][j] = (D[i - 1][j + 1] % div);
            else
                D[i][j] = (D[i - 1][j + 1] % div + D[i - 1][j - 1] % div) % div;
        }
    }
    int sum = 0;
    for (int i = 0; i <= 9; ++i)
    {
        sum += D[n][i];
        sum %= div;
    }
    printf("%d\n", sum % div);
    return 0;
}