9095: 1로 더하기

문제

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

풀이

import sys
input = sys.stdin.readline

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

    for i in range(4, n+1):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
        
    print(dp[n])

• dp[1] = 1 (1)
• dp[2] = 2 (1+1, 2)
• dp[3] = 4 (1+1+1, 2+1 / 1+2 / 3)
• dp[4] = 7 (1+1+1+1, 1+2+1, 2+1+1, 3+1 / 1+1+2, 2+2 / 1+3)

-> 1을 만드는 방법에 +3, 2를 만드는 방법에 +2, 3을 만드는 방법에 +1을 각각 해주면 된다.

일반화하면

• dp[k] = dp[k-3] + dp[k-2] + dp[k-1]