[python/파이썬] 백준 9461 파도반 수열

[문제 출처]

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

[문제 풀이]

문제에서 주어진 그림을 통해서 계속해서 다음 숫자를 구해보면

 

1 1 1 2 2 3 4 5 7 9 12 16 21 28.. 이런 식으로 쭉 이어진다.

구한 숫자들을 살펴보면 11122 이후에는 i-1번째와 i-5번째 합으로 i번째 숫자가 결정됨을 알 수 있다.

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())

    dp = [1,1,1,2,2]

    if n > 4:
        for i in range(5,n):
            dp.append(dp[i-1]+dp[i-5])

    print(dp[n-1])