(C++) - 백준(BOJ) 10884 : 쉬운 계단 수 답

//D[i][j] = i길이를 가진 수의 제일 마지막에 오는 수 j(0<=j<=9)

//D[i][j] = D[i-1][j-1](j-1>=0)+D[i-1][j+1](j+1<=9)

#include <iostream>
using namespace std;
long long D[101][10],N,ans;
int main() {
    
    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 - 1 >= 0) { D[i][j] += D[i - 1][j - 1]; }
            if (j + 1 <= 9) { D[i][j] += D[i - 1][j + 1]; }
            D[i][j] %= 1000000000;
        }
    }
    for (int i = 0; i <= 9; i++)
        ans += D[N][i];
    cout << ans % 1000000000;
}