[백준] 9461번 파도반 수열 (Python)

문제

 

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

코드

 

T = int(input())


for i in range(T):
    
    a=int(input())
    result = [0] * (a)
    
    for j in range(a):
        if j <= 2:
            result[j] = 1
        elif j <= 4:
            result[j] = 2
        else:
            result[j] = result[j-5] + result[j-1]
            
    print(result[a-1])

 

코드설명

 

1  1  1  2  2  3  4  5  7  9  12  16  21  28   => 변의길이
0  1  2  3  4  5  6  7  8  9  10  11  12  13   => 인덱스값

 

변의길이(인덱스값)

3(5) = 1(0) + 2(4)
4(6) = 1(1) + 3(5)
5(7) = 1(2) + 4(6)
7(8) = 2(3) + 5(7)
9(9) = 2(4) + 7(8)
12(10) = 3(5) + 9(9)
16(11) = 4(6) + 12(10)

 

 

점화식을 찾아야 쉽게 풀 수 있는 문제인것 같다.

0~4 까지는 특별한 규칙이 존재하지 않는것 같아 미리 리스트에 넣어준다.

5부터는 result[n] = result[n-5] + result[n-1] 점화식이 성립한다.