[Python] 백준 9461번: 파도반 수열 풀이

 

소스코드

T = int(input())
P = [0 for i in range(101)]
P[1] = 1
P[2] = 1
P[3] = 1
P[4] = 2
P[5] = 2
for i in range(T) :
    n = int(input())
    for j in range(6,n+1) :
        P[j] = P[j-1] + P[j-5]
    print(P[n])

 

주어진 그림을 보면, 

3 = 2 + 1

4 = 3 + 1

5 = 4 + 1

7 = 5 + 2

9 = 7 + 2 

임을 알 수 있다.

 

즉, P[6]번 째부터 P[n] = P[n-1] + P[n-5] 가 성립함을 알 수 있다.