9461: 파도반 수열

문제

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

풀이

import sys
input = sys.stdin.readline

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

    print(dp[n])

• 그림에서 해결 방법을 얻진 못했고, 점화식 규칙이 보여서 때려 맞추듯 풀었다.
• dp[k] = dp[k-3] + dp[k-2]

다른 풀이

• 그림으로부터 dp[k] = dp[k-5] + dp[k-1]이라는 점화식도 얻을 수 있다.