[dp/백준] 9461번: 파도반 수열

-문제:https://www.acmicpc.net/problem/9461

 

문제에 점화식을 유추할 수 있는 정보가 있어서 그걸 토대로 점화식을 작성한 후 코드를 작성하니 정답이 떴다

점화식: p(n)=p(n-3)+p(n-2)

 

-정답풀이:

각 테스트마다 쓰이는 dp는 달라야하므로 dp 초기화하는 것은 for문 안에다가 넣어준다 

t=int(input())

for _ in range(t):
    dp=[1,1,1]
    n=int(input())
    for i in range(3,n):
        dp.append(dp[i-3]+dp[i-2])
    print(dp[n-1])