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

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

15990번: 1, 2, 3 더하기 5

 

 이 문제는 Dynamic Programming, DP 알고리즘으로 해결할 수 있습니다. 

 

 dp[n]은 숫자 n을 1, 2, 3의 합으로 나타낸 모든 경우의 수를 나타냅니다.(단, 같은 수가 연속 되면 안됨)

 

 이 문제와 비슷한 문제인 9095번은 어떠한 조건도 없이 단지 1, 2, 3의 합으로 나타낸 모든 경우의 수를 찾으면 됩니다. (풀이: https://iridescent-zeal.tistory.com/19?category=1261302)

 

 이때의 점화식은 dp[n]=dp[n-1]+dp[n-2]+dp[n-3] 이었는데요. 

 

 하지만 이 문제에서는 '같은 수가 연속 되면 안 된다'는 조건이 붙었기 때문에 숫자 1, 2, 3에 더해지는 가능한 경우의 수를 나타낼 자료구조가 필요합니다. 

 

n	모든 경우(노란색만 가능)	{one, two, three)	dp[n] = 경우의 수
1	= 1	{1, 0, 0}	1
2	= 1 + 1 = 2	{0, 1, 0}	1
3	= 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3	{1, 1, 1}	3
4	= 1 + 3 ( = 1 + 1 + 2   = 1 + 2 + 1   = 1 + 3) = 2 + 2 = 3 + 1	{2, 0, 1}	3 =( 2 + 0 + 1)

 

 예를 들어 숫자 4는 1+2+1, 1+3, 3+1로 표현할 수 있습니다.

 

 이때 숫자 1에 더해질 수 있는 수(합해서 3)들의 경우의 수는 2+1, 3 두 가지 입니다. 이 변수의 이름을 one이라고 하겠습니다. 그렇다면 one=2가 됩니다. 

 

 그럼 이때 one을 어디서 가져올까요? 바로 dp[4-1]인 dp[3]에서 one을 제외한 two+three의 값이 됩니다. 

 

 2에 더해질 수 있는 수(합해서 2)들의 경우의 수는 없습니다. 4를 만들기 위해선 2에 2를 더해야 하는데 이때 2가 중복되기 때문입니다. 이 변수의 이름을 two라고 하겠습니다. 그렇다면 two=0이 됩니다. 

 

 two는 dp[2]의 one+three 겠지요!

 

 마찬가지로 3에 더해질 수 있는 수(합해서 1)들의 경우의 수는 1 하나 뿐 입니다. 그럼 변수 three=1이 되겠죠!

 

 역시 three는 dp[1]의 one+three 겠지요!

 

그럼 숫자 4를 1, 2, 3 더하기로 나타내는 방법은 one+two+three=3가지 입니다. 

 

점화식은 다음과 같습니다

 

dp[n].one=dp[n-1].two+dp[n-1].three

dp[n].two=dp[n-2].one+dp[n-2].three

dp[n].three=dp[n-3].one+dp[n-3].two

dp[n].n=dp[n].one+dp[n].two+dp[n].three

 

#include<iostream>
#include<algorithm>
#include<cstdlib>

#define buf 1000000009

using namespace std;

typedef class info {
public:
	long long n;
	long long one, two, three;

	info() {
		n = one = two = three = 0;
	};

	info(int N) {
		n = 1;
		if (N == 1) {
			one = 1;
			two = 0;
			three = 0;
		}
		else if (N == 2) {
			one = 0;
			two = 1;
			three = 0;
		}
		else if (N == 3) {
			n += 2;
			one = 1;
			two = 1;
			three = 1;
		}
	};
}info;

info dp[100001];

int main(void) {

	int t, n;
	info temp;

	temp = info(1);
	dp[1] = temp;
	temp = info(2);
	dp[2] = temp;
	temp = info(3);
	dp[3] = temp;

	cin >> t;
	
	while (t > 0) {

		cin >> n;

		if(dp[n].n == 0) {
			for (int i = 4; i <= n; i++) {

				if (dp[i].n != 0)
					continue;

				dp[i].one = (dp[i - 1].two + dp[i - 1].three) % buf;
				dp[i].two = (dp[i - 2].one + dp[i - 2].three) % buf;
				dp[i].three = (dp[i - 3].two + dp[i - 3].one) % buf;
				dp[i].n = (dp[i].one + dp[i].two + dp[i].three) % buf;

			}
		}

		cout << dp[n].n << endl;

		t--;
	}

	return 0;
}