9461 - 파도반 수열 [DP]

출처 : 백준 9461 파도반 수열

문제

파도반 수열 문제는 일정한 패턴을 보이는 삼격형 변의 길이를 구하는 문제이다.

N=5 까지는 특정한 패턴을 보이지 않다고 N=6부터는 패턴이 보이기 시작한다. 바로 이전 삼각형 변의 길이와 5개 index 이전의 삼각형의 변을 더한 값이 답이 된다. 6번째 삼각형부터 패턴이 보이기 때문에 이전까지의 값들은 미리 초기화해두고 그 뒤 값들만 계산을 하면 된다. 식으로 표현하면 다음과 같을 것이다: a[i] = a[i-1] + a[i-5]

풀이

import sys
r = sys.stdin.readline

N = int(r())
arr = [int(r()) for _ in range(N)]
seq = [1, 1, 1, 2, 2]

for i in range(5, max(arr)):
    seq.append(seq[i-1]+seq[i-5])

for i in arr:
    print(seq[i-1])