[백준/C++] 1, 2, 3 더하기 5

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

풀이

다음에 오는 숫자가 그 직전의 숫자에 의존하기 때문에 9095번처럼 경우의 수 하나만 가지고 점화식을 세우는 것이 불가능하다. 점화식에 필요한 인자를 하나 더 늘려서 마지막 숫자를 포함하도록 바꾸자. 만약 D[n][k]를 n을 k로 끝나도록 1, 2, 3의 합으로 나타내는 경우의 수라고 가정한다면,

D[n][k] = D[n - i][k가 아닌 다른 수] + D[i - j][k가 아닌 다른 수]

이런 식을 점화식을 세울 수 있다.

#include <iostream>
#include <cstring>
using namespace std;

long long MOD = 1000000009;
long long D[100001][4];

long long DP(int n)
{
	for(int i = 4; i <= n; ++i)
		for(int j = 1; j <= 3; ++j) {
			if(j == 1) D[i][j] = (D[i - j][2] + D[i - j][3]) % MOD;
			if(j == 2) D[i][j] = (D[i - j][1] + D[i - j][3]) % MOD;
			if(j == 3) D[i][j] = (D[i - j][1] + D[i - j][2]) % MOD;
		}

	long long sum = 0;
	for(int i = 1; i <= 3; ++i)
		sum += D[n][i];

	return sum % MOD;
}

int main()
{
	int C, n;
	cin >> C;
	memset(D, 0, sizeof(D));
	D[1][1] = 1; D[2][2] = 1; D[3][1] = 1; D[3][2] =1; D[3][3] = 1;

	while(C--) {
		cin >> n;

		cout << DP(n) << "\n";
	}

	return 0;
}

끝