[C++] 백준(BAEKJOON) 10844

#include <iostream>
#include <cstring> //memset
 
using namespace std;
const int MOD = 1000000000;
int cache[10][101]; //cache[digit][length], digit으로 시작하는 숫자, length는 길이
 
int dp(int digit, int length)
{
    if (digit < 0 || digit > 9) //한자리수만 가능
        return 0;
 
    if (cache[digit][length] != -1)
        return cache[digit][length];
 
    //다음 수를 하나 작은 수 혹은 하나 큰 수로
    return cache[digit][length] = (dp(digit - 1, length - 1) + dp(digit + 1, length - 1)) % MOD;
}
 
int main(void)
{
    int N;
    cin >> N;
 
    if (N < 1 || N > 100)
        exit(-1);
 
    memset(cache, -1, sizeof(cache));
 
    for (int i = 0; i < 10; i++)
        cache[i][1] = 1; //초기값(1~9까지는 1씩)
 
    int sum = 0;
 
    for (int i = 1; i <= 9; i++)
    {
        sum += dp(i, N); //0으로 시작하는 숫자는 없으므로 1부터
        sum %= MOD; //이 코드를 작성하지 않으면 틀렸다고 나옵니다.
    }
 
    cout << sum << endl;
 
    return 0;
}