[#알고리즘/Dynamic Programming/[백준]9461번: 파도반 수열(python)]

Question

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

Solution

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다.
이들의 규칙을 살펴보면 P(n) + P(n+1) = P(n+3) 수식의 관계를 확인할 수 있다.
즉, P(n) = P(n-3) + P(n-2) 관계로 나타낼 수 있다. 이렇게 점화식으로 나타낼 수 있는 문제들은 동적 프로그래밍 방법을 이용하여 문제를 해결하자.

Code

T = int(input())
N = [int(input()) for _ in range(T)]

d = [0] * 101
d[1] = 1
d[2] = 1

def pado(x) :
    for i in range(3, x + 1) :
        d[i] = d[i-3] + d[i-2]
        
    return d[x]

for x in N :
    print(pado(x))