[백준-9461] 파도반 수열 / Python

9461번: 파도반 수열

for _ in range(int(input())):
    n = int(input())
    d = [0] * 101
    d[1], d[2], d[3], d[4] = 1, 1, 1, 2
    for i in range(5, n + 1):
        d[i] = d[i - 2] + d[i - 3]
    print(d[n])

 

해설

규칙만 알면 쉽게 해결할 수 있는 dp문제였다.

2칸과 3칸 이전의 값을 합한 값이 현재 값이 된다.