[DP] boj 11057 - 오르막 수

백준 11057은 재귀로 풀면 recursion 에러가 난다. 호출 제한을 걸어둔 게 있기 때문에 그런데, 아래 코드로 제한을 늘릴 수 있다.

import sys
sys.setrecursionlimit(10000)

이렇게 해서 풀긴 했는데 재귀가 아닌 방법으로 다시 풀어야겠다.

 

재귀로 푼 방법

import sys
sys.setrecursionlimit(10000)

def calc(num, __cache = {1:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}):
    if num in __cache:
        return __cache[num]
    __cache[num] = []
    for i in range(1, 11):
        __cache[num].append(sum([calc(num-1)[j-1] for j in range(1, i+1)]))
    return __cache[num]

n = int(sys.stdin.readline())
print(sum(calc(n)) % 10007)