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

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[101][10]={};
#define mod 1000000000;

int main(void) {
    cin >> n;

    dp[1][0] = 0;
    for(int i=1; i<10; i++){ // 쉬운 계단수가 한자리인 경우 1로 초기화
        dp[1][i] = 1;
    }

    for(int i=2; i<=n; i++){
        dp[i][0] = dp[i-1][1]; // 마지막수가 0인 경우
        dp[i][9] = dp[i-1][8]; // 마지막수가 9인경우
        for(int j=1; j<9; j++){
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%mod;
        }
    }

    int result = 0;
    for(int i=0; i<10; i++){
        result = (result + dp[n][i])%mod;
    }
    cout << result << endl;

    return 0;
}