시간 2초, 메모리 512MB
input :
-
n (1 <= n <= 116)
output : -
n번째 수 출력
조건 : -
f(1) = f(2) = f(3) = 1
-
f(n) = f(n - 1) + f(n - 3)
DP로 3이하일때는 이미 저장되어 있는 1을 리턴하고.
DP에 이미 저장되어 있을 경우엔 DP의 값을.
그렇지 않다면 DP에 점화식을 이용해서 재귀를 걸자.
import sys
n = int(sys.stdin.readline())
dp = [-1] * (n + 1)
def recursion(start):
if start <= 3:
dp[start] = 1
return dp[start]
if dp[start] != -1:
return dp[start]
dp[start] = recursion(start - 1) + recursion(start - 3)
return dp[start]
recursion(n)
print(dp[n])
재귀를 시키는 부분이 헷갈리네.. 다시 봐야 겠다
