백준 15989. 1, 2, 3 더하기 4

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

import sys
input = sys.stdin.readline

t = int(input())
dp = [1] * 10001 # 1만으로만 구성되는 경우는 모두 공통으로 1이므로 1로 초기화

# dp[0] = 1인 이유는 아무것도 선택하지 않는 1가지 경우가 있기 때문.

for i in range(2,10001): # 1만으로만 구성되는 경우에 +2씩 해주면 됨
    dp[i] += dp[i-2]

for  i in range(3, 10001): # 1만으로만 구성되는 경우에 +3 해주면 됨
    dp[i] += dp[i-3]

for _ in range(t):
    n = int(input())
    print(dp[n])