[백준 10844] 쉬운 계단수 (DP) (C/C++)

#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 1000000000
 
int N;
int sum;
long long dp[110][11];
 
int solve(int cnt, int num)
{
    if(cnt == 1)
    {
        return num == 0 ? 0 : 1;
    }
    
    if(dp[cnt][num] != 0)
    {
        return dp[cnt][num];
    }
 
    if(num == 0)
    {
        dp[cnt][num] = solve(cnt-1, num+1) % MOD;
    }
    else if(num == 9)
    {
        dp[cnt][num] = solve(cnt-1, num-1) % MOD;
    }
    else
    {
        dp[cnt][num] = (solve(cnt-1, num-1) + solve(cnt-1, num+1)) % MOD;
    }
    
    return dp[cnt][num];
}
 
int main(void)
{
//    freopen("B10844_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i <= 9; i++)
    {
        sum = (sum + solve(N, i)) % MOD;        
    }
    
    cout << sum;
    
    return 0;
}