[백준 9095] 1,2,3 더하기

DP

n=int(input())

input_array=[]

for _ in range(n):
  input_array.append(int(input()))

dp=[0]*(max(input_array)+1)
dp[1]=1
dp[2]=2
dp[3]=4

for i in range(4,max(input_array)+1):
  dp[i]=dp[i-3]+dp[i-2]+dp[i-1]

for i in range(n):
  print(dp[input_array[i]])