문제 링크 : https://www.acmicpc.net/problem/9461
재귀와 DP를 이용해서 풀 수 있다. DP를 안 쓰면 시간 초과가 뜬다.
점화식은 다음과 같다: P(N) = P(N - 2) + P(N - 3)
계산 결과를 딕셔너리에 저장하고 나중에 다시 필요할 때 접근해서 가져오는 식으로 풀어서 시간을 줄일 수 있었다.
from sys import stdin
dp = {1 : 1, 2 : 1, 3 : 1}
def sequence(x):
if x in dp:
return dp[x]
else:
dp[x] = sequence(x - 2) + sequence(x - 3)
return dp[x]
t = int(stdin.readline())
for i in range(t):
n = int(stdin.readline())
print(sequence(n))