[백준 9461] 파도반 수열 with Python

문제 링크

www.acmicpc.net/problem/9461

9461번: 파도반 수열

풀이

import sys

t = int(sys.stdin.readline())
n = [int(sys.stdin.readline()) for _ in range(t)]
dp = [0]*101
dp[1] , dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2
for i in range(6, max(n)+1):
    dp[i] = dp[i-1] + dp[i-5]
for i in n:
    print(dp[i])

N >= 6일 때부터 P(N) = P(N-1) + P(N-5)라는 점화식이 성립한다.