10844.cpp

#include <cstdio>

#define MOD 1000000000

int main(){
    int n;
    scanf("%d", &n);
    
    // 2차원 배열을 초기화 해주지 않으면 오류가 난다!!!!
    int dp[101][11]={0,};
    for(int i=0;i<=9;i++) dp[1][i]=1;

    /* 
       dp[i][k]: i자릿수의 마지막 숫자가 k인 계단 수의 갯수
       이렇게 마지막 수로 dp식을 세우면 맨 앞에 0이 들어갈지 말지를 따져주지 않아도 된다!
       결국 점화식은 i-1자릿수이고 마지막 숫자가 k-1인 수일때 맨 뒤에 k를 붙여주는 경우 + 
       i-1자릿수이고 마지막 숫자가 k+1인 수일때 맨 뒤에 k를 붙이는 두 경우로 나뉜다.

       예외가 
       1. dp[i][0]일때 => 맨 뒤에 1을 붙이는 경우밖에 못 샌다. 맨 뒤에 -1을 붙일 수 없다
       2. dp[i][9]일때 => 맨 뒤에 8을 붙이는 경우밖에 못 샌다. 맨 뒤에 0(or 10)을 붙일 수 x.
    */
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][1]; //맨 뒤가 0일때 
        dp[i][10]=0;
        for(int j=0;j<=9;j++) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%MOD; // 맨 뒤가 1~8일때
    }

    int sum=0;
    for(int i=1;i<=9;i++) sum=(sum+dp[n][i])%MOD;
    printf("%d\n", sum);
}