1. 문제 설명

1, 2, 3 더하기 4

2. 문제 분석

점화식을 구해 dp를 푼다.

• dp(n, 1) = dp(n-1, 1)
• dp(n, 2) = dp(n-2, 1) + dp(n-2, 2)
• dp(n, 3) = dp(n-3, 1) + dp(n-3, 2) + dp(n-3, 3)
• dp(n) = dp(n, 1) + dp(n, 2) + dp(n, 3)

3. 나의 풀이

import sys

t = int(sys.stdin.readline().rstrip())

dp = [1 for _ in range(10001)]
for i in range(2, 10001):
    dp[i] += dp[i-2]
for i in range(3, 10001):
    dp[i] += dp[i-3]

for _ in range(t):
    n = int(sys.stdin.readline().rstrip())
    print(dp[n])