9095 1, 2, 3 더하기

9095번 1, 2, 3 더하기

1이 되는 경우의수 1

2가 되는 경우의수 1,1 / 2  2가지

3 : 1,1,1 / 1, 2 / 2, 1 / 3 3가지

.....

 

 이 공식을 이용하면 쉽게풀수있다.

dp = [0, 1, 2, 4]
for i in range(4, 12):
    dp.append(dp[i-1] + dp[i-2] + dp[i-3])

for i in range(0, int(input())):
    print(dp[int(input())])