#127 백준 파이썬 [9461] 파도반 수열 - 점화식

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

 

#Solution

피보나치 수열이 2항의 점화식이라면, 파도반 점화식은 5항의 점화식이다.

def padovan(i):
    if i == 1 or i == 2 or i ==3:
        return 1
    elif i == 4 or i == 5:
        return 2
    else:
        answer = 0
        temp_1 = 1
        temp_2 = 1
        temp_3 = 1
        temp_4 = 2
        temp_5 = 2
        for j in range(6, i + 1):
            answer = temp_5 + temp_1
            temp_1 = temp_2
            temp_2 = temp_3
            temp_3 = temp_4
            temp_4 = temp_5
            temp_5 = answer
        return answer
        
case = int(input())
for _ in range(case):
    N = int(input())
    print(padovan(N))