[10844] 쉬운 계단수

이름은 쉬운 계단수인데 전혀 쉽지 않았다. 처음에 1차원 배열안에 i자릿수로된 계단수의 갯수를 저장했는데 도저히 답이 안나와서 다르게 접근했다.

#include <cstdio>
using namespace std;
​
​
​
int main(){
    int N = 0;
    int mod = 1000000000;
    int d[101][11];
    scanf("%d",&N);
    
    for(int i = 1;i<10;i++){
        d[1][i] = 1;
    }
​
    for(int i = 2;i<=N;i++){
        for(int j = 0;j<10;j++){
            if(j == 0){
                d[i][j] = d[i-1][1];
                d[i][j] %= mod;
            }else if(j == 9){
                d[i][j] = d[i-1][8];
                d[i][j] %= mod;
            }else{
                d[i][j] = d[i-1][j-1] + d[i-1][j+1];
                d[i][j] %= mod;
            }
        }
    }
​
    int res = 0;
    for(int j = 0;j<10;j++){
        res += d[N][j];
        res %= mod;
    }
    printf("%d\n",res);
}

i번째 자릿수를 가진 계단수중 끝자리가 j인 계단수들을 d[i][j 에 저장했다.

끝자리가 0인경우는 i-1번째 자릿수의 끝자리가 1일때와 그 수가 같다.끝자리가 8인경우는 i-1번째 자릿수의 끝자리가 9일때와 그 수가 같다.
나머지는 i-1번째 자릿수의 j-1과 j+1의 수를 합한 수와 같다.(ex. j == 4일때 i-1의 3(j-1)과 5(j+1)다음에 4가 올 수 있으므로)