[백준] 15989. 1, 2, 3 더하기 4 / 파이썬(python)

import sys
t=int(sys.stdin.readline())
dp=[0]*10001
dp[1]=1
dp[2]=2
dp[3]=3
for i in range(t):
    n=int(sys.stdin.readline())
    for j in range(4,n+1):
        dp[j]=(j//2)+1+dp[j-3]
    print(dp[n])

#n=1일때: 1 ->1개
#n=2일때: 2 , 11 ->2개
#n=3일때: 111,12,3 ->3개
#n=4일때: 1111,112,22,31 ->4개=3+f(1)
#n=5일때: 11111,1112,122, 113, 23 -> 5개=3+f(2)
#n=6일때: 111111,11112,1122,123,1113,222,33 ->7개=4+f(3)
#n=7일때 -> 8개=4+f(4)
#n=8일때 -> 10개=5+f(5)

#또 다른 방법
#d[i]+=dp[i-2]했을 때 dp=[1 1 2 2 3 3 4 4 5 5 6 6....]
#d[i]+=dp[i-3]했을 때 dp=[1 1 2 3 4 5 7 8 10 12 14....]