문제

문제 링크 : 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))