🔥

문제

정수 n이 주어졌을 때, n을 3이하의 수(1, 2, 3)들의 합으로 표현할 수 있는 가지수를 구해보자.


예를 들어, 3은 아래와 같이 4가지 방법으로 표현할 수 있다.


3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3

입력

첫째 줄에 테스트케이스의 개수 T가 주어진다.


둘째 줄부터 T - 1번째 줄까지 1, 2, 3의 합으로 표현할 정수 n이 주어진다. (1 ≤ n ≤ 11)

출력

첫째 줄부터 T번째 줄까지 각각의 테스트케이스에 대한 답을 출력한다.

예제 1 입력

3
1
3
5

예제 1 출력

1
4
13

Source

dp = [0 for _ in range(12)]

dp[1] = 1
dp[2] = 2
dp[3] = 4

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

t = int(input())
for i in range(t):
	print(dp[int(input())])

참고