[백준 15990] 1, 2, 3 더하기 5 (C++)

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

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로 나눈 나머지를 출력한다.

 

문제 풀이

---

dp 문제.

1~3까지는 미리 구해 배열에 채워 놓는다.

n(4이상)을 만들 수 있는 경우의 수는 (1) n-1을 만드는 모든 경우의 수의 마지막에 1을 더한 것, (2)  n-2을 만드는 모든 경우의 수의 마지막에 2를 더한 것, (3) n-3을 만드는 모든 경우의 수의 마지막에 3을 더한 것이 있다.

같은 수를 연속으로 사용하면 안되므로 (1)의 경우 n-1를 만드는 경우의 수 중 2로 끝나는 것, 3으로 끝나는 것만을 더해주면 된다. (2)의 경우 n-2를 만드는 경우의 수 중 1, 3으로 끝나는 것만을 더해주면 된다. (3)의 경우는 n-3을 만드는 경우의 수 중 1, 2로 끝나는 것만을 더해주면 된다.

즉, N을 만들 때 맨 마지막에 1~3을 더한 것을 각각 [N][1], [N][2], [N][3]이라 할 때

[N][1] = [N-1][2] + [N-1][3]

[N][2] = [N-2][1] + [N-2][3]

[N][3] = [N-3][1] + [N-3][2] 이 성립한다.

2차원 배열을 이용해 각 숫자를 채운 후 답을 출력하면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;
long long** dp;

void fillDpArr()
{
	dp = new long long* [100001];
	for (int i = 0; i < 100001; i++)
	{
		dp[i] = new long long[4];
		for (int j = 0; j < 4; j++)
		{
			dp[i][j] = 0;
		}
	}
	dp[1][1] = 1;
	dp[2][2] = 1;
	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;
	for (int i = 4; i < 100001; i++)
	{
		dp[i][1] = dp[i - 1][2] % 1000000009 + dp[i - 1][3] % 1000000009;
		dp[i][1] %= 1000000009;
		dp[i][2] = dp[i - 2][1] % 1000000009 + dp[i - 2][3] % 1000000009;
		dp[i][2] %= 1000000009;
		dp[i][3] = dp[i - 3][1] % 1000000009 + dp[i - 3][2] % 1000000009;
		dp[i][3] %= 1000000009;
	}
}

int main()
{
	fillDpArr();
	int T, num;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> num;
		long long sum = dp[num][1]+ dp[num][2]+ dp[num][3];
		sum %= 1000000009;
		cout << sum << "\n";
	}
	return 0;
}