10844 쉬운 계단 수

BOJ::10844 쉬운 계단 수

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

n자리수에 대해

0로 끝나는 수,

1로 끝나는수

.

.

.

9로 끝나는 수 를 기록하며 점화식 세웠다.

특히 마지막자리가 0인경우와 9인경우는 마지막에서 2번째 자리수가 1,8로 고정이므로

두 경우만 예외처리 하였다.

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