[BOJ 9095] 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

1, 2, 3의 경우만 생각하여 풀면 된다.

 

4는 3 + [1], 2 + [2], 1 + [3] ([n]은 n을 만들 수 있는 경우의 수) 로 볼 수 있다.

------

3 + (1)

2 + (2), 2 + (1 + 1)

1 + (3), 1 + (2 + 1), 1 + (1 + 2), 1 + (1 + 1 + 1)

------

즉, 어떤 수 n에 대하여 n을 1, 2, 3을 이용하여 만드는 경우의 수는

 

n-1의 경우의 수, n-2의 경우의 수, n-3의 경우의 수를 다 더한 것과 같다.

 

1, 2, 3의 경우의 수를 처음에 초기화해 놓고 이를 이용하여 n번째 수의 경우의 수를 구하면 된다.

---

#include <stdio.h>


int DP[11];
int main()
{

	int T, n;
	scanf("%d", &T);

	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;

	for (int i = 0; i < T; i++)
	{
		scanf("%d", &n);
		for (int j = 4; j <= n; j++)
			DP[j] = DP[j - 1] + DP[j - 2] + DP[j - 3];
		printf("%d\n", DP[n]);
	}
}