[Python] 파도반 수열 - 백준 (DP)

해당 글은 백준 9461번 문제 '파도반 수열'을 다룬다.

문제

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

9461번: 파도반 수열

 

설명

해당 문제는 DP로 풀면 쉽게 해결할 수 있다.

4번째 값 이후부터는 4-3번째 값과 4-2번째 값을 더한 수열이 반복되므로, 이를 활용하여 점화식을 표현하면 아래와 같다.

# result[1], result[2], result[3]은 모두 1
result[i] = result[i-3]+result[i-2]  # i >= 4

여기서는 테스트케이스마다 result를 구해서 출력해주었는데,

100까지의 모든 result를 계산한 뒤 result[n]만 출력해줘도 될 듯 싶다!

 

코드

T = int(input())

result = [0]*101
for t in range(T):
    n = int(input())
    result[1] = 1
    result[2] = 1
    result[3] = 1
    if n >= 4:
        for i in range(4, n+1):
            result[i] = result[i-3]+result[i-2]
    print(result[n])