10844번 쉬운 계단 수

일단 N=1일 경우 1층부터 9층까지 9개가 존재한다.

 

N=2일 경우 0층으로 갈 수 있는 경우는 그 전 1층에서 가는 경우밖에 없다.

                   9층으로 갈 수 있는 경우는 그 전 8층에서 가는 경우밖에 없다.

                   1층에서 8층으로 갈 수 있는 경우는 그 전 층의 +1, -1층 즉, 2가지 경우가 있다.

 

따라서 N 길이를 가려고 했을 때 F[n][0] = F[n-1][1]

                                           F[n][9] = F[n-1][8]

                                           F[n][1] = F[n-1][0] + F[n-1][2]

                                           .....

                                           ...

                                           ..

                                           F[n][8] = F[n-1][7] + F[n-1][9]

 

층수를 J라고 하면 F[n][j] = F[n-1][j-1] + F[n-1][j+1] 이 식이 성립하게 된다.

 

ps. N=2일 경우 1층으로 가는 경우는 전 0층과 2층인데 0층에서 시작을 할 수 없다. 그래서 따로 2층인 경우를 나누려고 했으나 N=1일 때 0층의 값이 0이기 때문에 할 필요가 없었다.

 

#include <iostream>
#define MAX 101
#define mod 1000000000
using namespace std;

long long dp[MAX][10];

long long stair(int num){
    int sum=0;
    
    for(int j=1;j<=9;j++){
        dp[1][j]=1;
    }
    
    for(int i=2;i<=num;i++){
        dp[i][0]=dp[i-1][1]%mod;
        dp[i][9]=dp[i-1][8]%mod;
        for(int j=1;j<=8;j++){
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]%mod;
        }
    }
    
    for(int i=0;i<=9;i++){
        sum=(sum+dp[num][i])%mod;
    }
    
    return sum%mod;
}
int main(){
    int num;
    cin >> num;
    cout << stair(num) << endl;
}