[9095] 1,2,3 더하기 in python

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

 

dp[1] = 1가지

dp[2] = 2 , 1+1 = 2가지

dp[3] = 3, 2+1, 1+2, 1+1+1 = 4가지

dp[4] = 3+1, 2+1+1, 1+2+1, 2+2, 1+3, 1+1+2, 1+1+1+1 = 7가지 (1+2+4)

dp[5] = 13가지 (2+4+7)

t=int(input())
dp=[0 for _ in range(11)]
dp[1]=1
dp[2]=2
dp[3]=4
for _ in range(t):
    n=int(input())
    if n < 4:
        print(dp[n])
    else:
        for i in range(4,n+1):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        print(dp[i])