1, 2, 3을 사용할 수 있으므로 n-1, n-2, n-3
의 숫자는 모두 n
으로 만들 수 있다.
따라서, 먼저 dp[1], dp[2], dp[3]의 초기 값을 구해준다.
이때 조심해야할 점은 dp크기를 n+3크기로 동적할당해줘야 초기화시 에러가 나지 않는다.
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
t = int(input())
for _ in range(t):
n = int(input())
dp = [0]*(n+3)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])