[C++] BOJ / 15988번 / 1, 2, 3 더하기 3

15988번: 1, 2, 3 더하기 3

 

- 풀이

문제에 나와 있는 조건을 바탕으로 경우의 수를 작성해보면 다음과 같다.

 

DP[1] = (1)
DP[2] = (2), (1 + 1)
DP[3] = (3), (1 + 2), (2 + 1), (1 + 1 + 1)
DP[4] = (1 + 3), (3 + 1), (2 + 2), (1 + 1 + 2), (1 + 2 + 1), (2 + 1 + 1), (1 + 1 + 1 + 1)

 

여기서 DP[i]란 i를 1, 2, 3의 합으로 나타내는 방법의 수를 의미하며 따라서 DP[1] = 1, DP[2] = 2, DP[3] = 4, DP[4] = 7 이라고 할 수 있다. 여기서 DP[4]에 대해서 좀 더 자세히 살펴보면 다음과 같다.

 

DP[4]의 경우 DP[3]의 경우에서 숫자 1을 더하면 얻을 수 있다. 즉, DP[3]은 1, 2, 3의 합으로 숫자 3을 나타낼 수 있는 방법의 집합이기 때문에 각각의 경우에 1만 더해준다면 숫자 4를 만들어낼 수 있다는 뜻이다.

위와 같은 방식으로 DP[2]의 경우에 숫자 2를 더해주면 역시나 숫자 4를 만들어낼 수 있고, DP[1]의 경우에 숫자 3을 더해주면 숫자 4를 만들어낼 수 있다. 이러한 규칙을 점화식으로 나타내면 다음과 같다.

 

DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3]

 

해당 점화식을 코드로 구현해주는 방식으로 풀이하였습니다.

해당 문제의 경우 지속적으로 나머지 연산을 수행해주어야 하며 값이 매우 커질 수 있기 때문에 자료형을 long long 형으로 지정해주어야 정답이 될 수 있습니다.

---

#include <iostream>

using namespace std;

#define MAX 1000000
#define MOD 1000000009
#define ll long long
#define endl '\n'

ll DP[MAX];

int main()
{
	int t;

	cin >> t;

	DP[1] = 1; DP[2] = 2; DP[3] = 4;
	while (t--)
	{
		int n;

		cin >> n;

		for (int i = 4; i <= n; ++i)
			DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % MOD;

		cout << DP[n] << endl;
	}
}