[백준/C,C++] 10844번: 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

1자리에 해당하는 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9입니다. 2자리에 해당하는 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98입니다. 즉, 1 뒤에 올 수 있는 숫자가 2개, 2 뒤에 올 수 있는 숫자가 2개 이런 식으로 붙어 약 2배씩 늘어납니다. 1의 경우엔 0과 2, 2의 경우엔 1, 3 이런 식이죠. 그래서 2자리에 해당하는 계단 수중 다시 0으로 끝나는 수는 1로 끝나는 1자리 계단 수의 개수와 같고, 1로 끝나는 수는 0으로 끝나거나 2로 끝나야 하므로 0으로 끝나는 1자리 계단 수와 2로 끝나는 1자리 계단 수의 합과 같습니다. 각 자리별로 계단 수를 마지막에 끝나는 숫자에 따라 개수를 세보면 아래 표와 같습니다. 참고로 9로 끝나는 계단수도 이전 자리의 계단 수 중 8로 끝나는 계단 수의 개수와 같습니다.

	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2
4	3	4	7	7	8	8	8	7	6	3

즉 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]와 같이 나타낼 수 있는데, 0과 9는 각 1과 8 이후로만 올 수 있으니 예외처리를 해주면 됩니다.

#include<iostream>

using namespace std;

#define MAX 101

long long DP[MAX][10];

int main(void)
{
    int N; 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] % 1000000000;
            else if (j == 9) DP[i][j] += DP[i - 1][8] % 1000000000;
            else {
                DP[i][j] += DP[i - 1][j - 1] % 1000000000;
                DP[i][j] += DP[i - 1][j + 1] % 1000000000;
            }
        }
    }

    long long sum = 0;
    for (int i = 0; i <= 9; i++) {
        sum += DP[N][i];
    }

    cout << sum % 1000000000;

    return 0;
}