쉬운 계단 수 10844

문제

접근 방법

1인 경우 1~9까지의 자연수가 계단 수이다.
2인 경우 계단 수를 확인해보자.

0	1	2	3	....	7	8	9
1	0,2	1,3	2,4	....	6,8	7,9	8

17개의 경우가 나온다.

3인 경우 계단 수를 확인해보자.
010 012
101 121 123
210 212 232 234
321 323 343 345
....
765 767 787 789
876 878 898
987 989
32개의 경우가 나온다.
대략 계단의 모양으로 만들어진다는 것을 볼 수 있다.

0101 0121 0123
1010 1012 1210 1212 1232 1234
2101 2121 2123 2321 2323 2343 2345
3210 3212 3232 3234 3432 3434 3454 3456

예측대로라면 61개의 경우가 나올 것이다.
규칙을 생각해내야 한다.
표로 나타내보면 좋다.

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

숫자를 맨 뒤에 붙인다고 생각하면 고려할 것이 많다.
그렇다면 앞에 숫자를 정하고 뒤에 숫자를 붙인다고 생각하면 어떨까?
N이 3일 때 1을 생각해보면 0, 1로 시작하는 값을 붙이면 된다. 이미 완성된 값은 N이 2일 때 1에서 존재한다.
즉 [N,M]=[N-1][M-1]+[N-1][M+1]인 것이다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int main()
{
    int N, sum = 0;
    scanf("%d", &N);
    vector<vector<int>> dp(N, vector<int>(10, 1));
    for (int i = 1; i < N; ++i)
    {
        dp[i][0] = dp[i - 1][1];
        for (int j = 1; j < 9; ++j)
        {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
        }
        dp[i][9] = dp[i - 1][8];
    }
    for (int i = 1; i <= 9; ++i)
    {
        sum = (sum + dp[N - 1][i]) % 1000000000;
    }
    printf("%d", sum);
    return 0;
}

풀이

DP의 경우 앞이나 뒤에 붙이는 경우가 많은 것 같다. 뒤에 붙이기 힘들 거 같으면 앞에 붙이는 경우를 생각해보면 좋다.
오랜만에 scanf, printf를 사용해봤다.