[백준 C++] 9095 : 1, 2, 3 더하기

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

DP는 점화식.

 

1과 2, 3으로 구성되어 나타내는 방법을 구하는 문제이다.

점화식을 생각해 내는 것이 어렵지만 1, 2, 3을 사용하는 점을 생각하여 도출해 내야 한다.

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> answer = vector<int>(12, -1);

void cal()
{
	answer[1] = 1;
	answer[2] = 2;
	answer[3] = 4;

	for (int i = 4; i < 12; i++)
		answer[i] = answer[i - 3] + answer[i - 2] + answer[i - 1];
}

int main()
{
	int T;
	cin >> T;

	cal();

	for (int i = 0; i < T; i++)
	{
		int input;
		cin >> input;

		cout << answer[input] << '\n';
	}

	return 0;
}

하나의 수에 대해 방법을 구할 때에 처음에 1이 오게 되면, 남은 숫자는 N - 1의 방법 합이 된다.

2가 오게 되면, 남은 숫자는 N - 2의 방법 합이 된다.

3이 오게 되면, 남은 숫자는 N - 3의 방법 합이 된다.

우리는 모든 방법의 수를 구하는 것이기 때문에 이를 활용하면 된다.

 

1과 2와 3은 방법이 많지 않으므로 미리 구해서 넣어주고, 위에서 설명한 점화식을 넣어주면 풀 수 있는 문제이다.