[파이썬]백준 9461 파도반 수열

링크

백준 9461 파도반 수열

DP문제이다.
점화식도 쉽게 구해지고 사실상 피보나치 문제랑 같은문제이다.

정답 코드

def dp(n):
    if n < 3:
        return 1
    if n >= 3 and memo[n] == 0:
        memo[n] = dp(n - 3) + dp(n - 2)
    return memo[n]

for _ in range(int(input())):

    N = int(input())
    memo = [0] * 100
    for i in range(3):
        memo[i] = 1
    dp(N - 1)
    print(memo[N - 1])

알게된 것👨‍💻

• 점화식을 구하는 것이 중요하다