백준 9095 - 1, 2, 3 더하기

1부터 차례대로 나올 수 있는 방법을 나열해서 보면 좋습니다.

위 사진을 보면 1,2,3을 이용해 4를 만드는 조합의 수는 3을 만드는 조합에서 1을 더한 것과 2를 만드는 조합에서 2를 더한 것과 1을 만드는 조합에서 3을 더한 것을 모두 합치면 됩니다.

즉, 아래 식이 만들어집니다.

1, 2, 3을 만드는 수는 해당 식이 성립하지 않으니 직접 넣어줘야 합니다.

#include <iostream>
#include <vector>

int main()
{
	int caseCnt;
	std::cin >> caseCnt;

	for (int i = 0; i < caseCnt; i++)
	{
		int num;
		std::cin >> num;
		std::vector<int> cnts(12);

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

		for (int j = 4; j <= num; j++)
			cnts[j] = cnts[j - 1] + cnts[j - 2] + cnts[j - 3];

		std::cout << cnts[num] << "\n";
	}

	return 0;
}