파도반 수열

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

❗문제 정리
다이나믹 프로그래밍

📑코드

t=int(input())#테스트 케이스의 수
n=[]
for i in range(t):
    n.append(int(input()))

res=[1,1,1,2,2,3,4,5,7]+[0]*101

for i in range(3,max(n)+1):
    res[i]=res[i-2]+res[i-3]

for n_ in n:
    print(res[n_-1])

📝코드 설명

순열의 순서가 11 1 2 2 3 4 5 7 9 12 16...순으로 늘어나기 때문에 이를 이용.
이미 계산한 값을 뽑아오는 형태

🎖제출 결과

💡insight
https://en.wikipedia.org/wiki/Padovan_sequence