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

import sys
 
test_case = int(input())
triangle_list = [1,1,1,2,2] # 초기 값
for case in range(test_case):
    num = int(sys.stdin.readline().strip())
    if len(triangle_list) >= num:
        print(triangle_list[num-1])
    else:
        index = len(triangle_list)
        for i in range(index, num):
            triangle_list.append(triangle_list[i-1] + triangle_list[i-5])
        print(triangle_list[num-1])

# 새롭게 그려지는 삼각형의 한변의 길이는 이전 삼각형과 다섯번째 전 삼각형의 변의 길이의 합과 같다.

반복적인 계산을 피하기 위해 동적 프로그래밍을 사용한다.