[백준] [C/C++] [★] 15990번 : 1,2,3 더하기 5

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

3
9
27

알고리즘 [ 접근 방법 ]

다이나믹 프로그래밍 문제이다. 간단해 보이지만 같은 수를 두번 이상 연속해서 사용하면 안된다는 조건때문에 까다로운 문제이다.

위의 조건이 없다면 문제의 점화식은 다음과 같다. d[N] = 정수 N을 1,2,3의 합으로 나타내는 방법의 수 d[N] = d[N-1]+d[N-2]+d[N-3] 여기에 같은 수를 두번 이상 연속해서 사용하면 안된다는 조건을 어떻게 붙일까?

연속, 증가, 감소라는 조건이 나왔을 때는 연속한 두개의 수를 살펴보면 된다.

만약 마지막에 더한 수가 +1이라면 그 앞에 올 수 있는 수는 +2,+3일 것이고, 마지막에 더한 수가 +2이라면 그 앞에 올 수 있는 수는 +1,+3, 마지막에 더한 수가 +3이라면 그 앞에 올 수 있는 수는 +1,+2일 것이다.

이를 점화식으로 나타내면, d[N][j] = 정수 N을 1,2,3,의 합으로 나타내는 방법의수, 마지막 수가 j인 경우

이를 코드로 구현하면 된다.

사실 이를 생각해내는것은 그다지 어렵지 않았지만, 실제 이를 코드로 구현해낼때 어떤방식으로 구현해야 할지 헷갈려 풀지 못하고 답안을 살펴봤다. DP문제를 좀 더 풀어보고 나중에 다시한번 풀어봐야 할 것 같다.

풀이

#include <iostream>
using namespace std;

long long int d[1000001][4]; // N이 주어졌을때 1,2,3의 합으로 나타나는 방법의 수, j= 맨뒤에 나온 수
const long long mod = 1000000009LL;
const int limit = 100000;

int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int test;
	cin >> test;

	int num;

	for (int i = 1; i <= limit; i++) {
		if (i - 1 >= 0) {
			d[i][1] = d[i - 1][2] + d[i - 1][3];
			if (i == 1) d[i][1] = 1;
		}

		if (i - 2 >= 0) {
			d[i][2] = d[i - 2][1] + d[i - 2][3];
			if (i == 2) d[i][2] = 1;
		}

		if (i - 3 >= 0) {
			d[i][3] = d[i - 3][1] + d[i - 3][2];
			if (i == 3) d[i][3] = 1;
		}

		d[i][1] %= mod;
		d[i][2] %= mod;
		d[i][3] %= mod;
	}

	while (test--) {
		cin >> num;
		long long int res = (d[num][1] + d[num][2] + d[num][3]) % mod;
		cout << res << endl;
	}


}