11057번 오르막 수

문제 링크

오르막 수

문제 풀이

현재 수보다 크거나 같은 수만 다음 수로 올 수 있다. 따라서 현재 수에서 9 까지 for문을 돌면서 재귀 호출을 해준다. index가 N 일때, 즉 길이가 N인 수를 만들었을 때를 기저 사례로 둔다.

구현

#include <iostream> 
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0;
const int MOD = 10007;

int N, cache[1001][11];

int solve(int index, int number) {
    if (index == N) return 1;

    int& ret = cache[index][number];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = number; i < 10; ++i) 
    	ret = (ret + solve(index + 1, i)) % MOD;
    return ret % MOD;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    memset(cache, -1, sizeof(cache));

    cout << solve(0, 0);;
    return 0;
}