[파이썬/python] 백준 9461번 : 파도반 수열(🥈3)

 

 

 

import sys
input = sys.stdin.readline

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

p(1) 부터 p(10)은 1,1,1,2,2,3,4,5,7,9 이다. 

규칙을 잘 살펴보면 p(n) + p(n+1) === p(n+3) 의 형태로 된 것을 볼 수 있다.

이것을 이용하여 dp.append((dp[-2] + dp[-3]))를 배열에 계속 추가하는 방식으로 풀이하였다.