파이썬) 파도반 수열 - BOJ

https://www.acmicpc.net/status?user_id=dlwnsgml203&problem_id=9461&from_mine=1

t = int(input())


for _ in range(t):
    dp = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
    n = int(input())
    if n <= 10:
        print(dp[n])
    else:
        for i in range(11, n+2):
            num = dp[-2] + dp[-3]
            dp.append(num)
        print(dp[n])

이 문제의 경우 굉장히 쉬운 문제이다.

이미 문제에서부터 dp를 이용하라고 dp[10]번째까지 문제에 나와있었다.

dp[n] = dp[n-2] + dp[n-3] 을 이용해 풀면 손쉽게 풀 수 있다.