baekjun 10844. 쉬운 계단 수

 계단을 오를 때 integer overflow를 방지하기 위하여 나머지를 더하는 문제.

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N;
int cache[101][10];
 
int letsBin(int level, int last) {
    if (level == N)
        return 1;
    int & ret = cache[level][last];
    if (ret != -1)
        return ret;
    ret = 0;
    
    if (last == 0) {
        ret += letsBin(level + 1, last + 1);
        ret %= 1000000000;
    }
        
    else if (last == 9) {
        ret += letsBin(level + 1, last - 1);
        ret %= 1000000000;
    }
        
    else {
        ret += letsBin(level + 1, last - 1) + letsBin(level + 1, last + 1);
        ret %= 1000000000;
    }
        
    
    return ret;
}
 
int main() {
    cin >> N;
    int result = 0;
    memset(cache, -1, sizeof(cache));
    for (int i = 1; i < 10; i++) {
        result += letsBin(1, i);
        result %= 1000000000;
    }
        
    cout << result  << endl;
    //system("pause");
    return 0;
}