백준 10844번 - 쉬운 계단 수

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

인접한 수의 차이가 1인 것에 착안하여, 
n 번째에서 5라는 수가 있을 때의 경우의 수는 n-1 번째에서 4와 6이라는 수가 있을 때의 경우의 수의 합으로 계산하였다.


점화식은 다음과 같다.

dp[k][n] = dp[k-1][n-1]+dp[k+1][n-1]

(n 번째에서 k 값일 때의 쉬운 계단수)

이때 k 값이 0과 9일 경우에는 -1과 10값을 포함시키면 안 되기 때문에 두 개의 값만 따로 계산하면 된다.

#include <iostream>
using namespace std;
 
 
int main(){
    
    int N,ans=0;
    cin>>N;
    
    int dp[10][101]={0};
    for(int i=1;i<=9;i++)
        dp[i][1]=1;
    
    for(int i=2;i<=N;i++){
        
        dp[0][i]=dp[1][i-1];
        dp[9][i]=dp[8][i-1];
        
        for(int j=1;j<=8;j++){
            dp[j][i]=(dp[j-1][i-1]+dp[j+1][i-1])%1000000000;
        }
    }
    
    for(int i=0;i<10;i++){
        ans+=dp[i][N];
        ans%=1000000000;
    }
    
    cout<<ans<<endl;
    return 0;
}