10844 쉬운 계단수

#include <stdio.h>
 
long long dp[105][11] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int j = 1; j <= 9; j++) {
        dp[1][j] = 1;
    }
 
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 8; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])%1000000000;
        }
        dp[i][0] = dp[i - 1][1]%1000000000;
        dp[i][9] = dp[i - 1][8]%1000000000;
    }
    
    long long sum = 0;
    for (int j = 0; j <= 9; j++) {
        sum += dp[n][j];
        sum %= 1000000000;
    }
 
    printf("%lld", sum);
}