9095

9095.cpp

#include <iostream>

/*

이 문제는 정수 n이 1, 2, 3의 조합으로 나타내는 문제이다.
n을 (n-1) + 1, (n-2) + 2, (n-3) + 3의 세 가지 방법으로 나타낼 수 있으므로
이 문제는 다이나믹 프로그래밍(DP)를 이용해서 풀 수 있다.

D[n] = n이 1, 2, 3의 덧셈 조합으로 나올 수 있는 경우의 수

덧셈 조합에서 맨 마지막으로 나올 수 있는 수의 경우의 수는 1, 2, 3이다.
	ex) 4 = 2 + 1 + '1' / 2 + '2' / 1 + '3'
	
따라서 D[n] = D[n-1] + D[n-2] + D[n-3]으로 나타낼 수 있다.

*/

int main()
{
	int n, t;
	int d[13] = { 0, };
	d[0] = 1;

	for (int i = 1; i < 11; i++)
	{
		if (i - 1 >= 0) d[i] += d[i - 1];
		if (i - 2 >= 0) d[i] += d[i - 2];
		if (i - 3 >= 0) d[i] += d[i - 3];
	}

	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		printf("%d\n", d[n]);
	}
}