(C++) 백준 9095번 - 1, 2, 3 더하기

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

문제

> 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
6. 1+3
7. 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구해라.

접근

N을 1, 2, 3의 합으로 나타내야하므로 DP를 사용해 DP(1), DP(2), DP(3)을 구해 계산하면 된다.

문제해결

> 1,2,3을 이용해 구하라고 했으므로 DP(1), DP(2), DP(3)을 구한다. 구한 각각의 경우의 수로 규칙을 찾는다.
> DP(4)를 보면 DP(3)일 때의 경우의 수의 앞에 각각 1이 붙어있고 DP(2)일 때의 경우의 수 앞에 2가, DP(1) 앞에 3이 붙어있다.
> DP(5)일 땐 DP(4) 앞에 1이, DP(3)앞에 2가, DP(2)앞에 3이 붙어있다. 결론적으로 앞에 1,2,3이 더해져 있을 뿐이지 경우의 수는 결국 DP(4), DP(3), DP(2)의 합이라는 뜻이다.
> 이를 수식으로 쓰면 DP(4) = DP(3) + DP(2) + DP(1)이고, DP(5) = DP(4) + DP(3) + DP(2) 이다. DP(4)는 앞선 DP(4)에 대한 수식이 대입될 수 있다.
> 결론적으로 DP(N) = DP(N-1) + DP(N-2) + DP(N-3)이다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T, N;
	cin >> T;
	vector<int> DP(11);
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;
	for (int i = 4; i < 11; i++)
		DP[i] = DP[i - 3] + DP[i - 2] + DP[i - 1];
	while (T--)
	{
		cin >> N;
		cout << DP[N]<< '\n';
	}
}

후기

언제나 DP는 규칙을 찾는게 가장 까다롭다. 규칙만 찾으면 쉽게 풀리는데 그게 힘들다..