[백준 15989] 1, 2, 3 더하기 4

문제 링크 => 15989번: 1, 2, 3 더하기 4 (acmicpc.net)

15989번: 1, 2, 3 더하기 4

---

다이나믹 프로그래밍 문제이다.

 

합을 나타낼 때 수를 1개 이상 사용한다는 것을 못봐서 약간의 뇌절을 했던 문제이다.

 

그럼 규칙성을 발견해보도록 한다.

 

• dp_1[x] => x = 1 + ( ) (( ) 안에 1, 2, 3 으로 구성)로 나타낼 때, ( ) 가 나타낼 수 있는 갯수 
• dp_23[x] => x = 2 + ( ) (( ) 안에 2, 3으로 구성) 또는 x = 3 + ( ) (( ) 안에 3으로 구성)로 나타낼 때, ( ) 가 나타낼 수 있는 갯수 
• dp[x] => dp_1[x] + dp_23[x] 

 

1 = 1   <= dp_1[1] = 0, dp_23[1] = 0

 

2 = 2 = 1 + (1)   <= dp_1[2] = 1, dp_23[2] = 0

 

3 = 3 = 1 + (1 + 1 , 2)   <= dp_1[3] = 2, dp_23[3] = 0

 

4 = 1 + (1 + 1 + 1, 1 + 2, 3)= 2 + (2)   <= dp_1[4] = 3, dp_23[4] = 1   

 

5 = 1 + (1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2) = 2 + (3)   <=  dp_1[5] = 4, dp_23[5] = 1

 

6 = 1 + (1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 2 = 1 + 1 + 3 = 1 + 2 + 2 = 2 + 3) = 2 + (2 + 2) = 3 + (3)   <= dp_1[6] = 5, dp_23[6] = 2

 

여기서 알 수 있는 규칙은 다음과 같다.

 

1. dp_23[x] = dp_23[x - 2] + (x % 3 == 0 ? 1 : 0)   <= x >= 6 일때 성립하므로 임시로 dp_23[2] = dp_23[3] = 1로 설정해둠

 

2. dp_1[x] = dp_1[x - 1] + dp_23[x - 1]

 

그런데, 1, 2, 3 으로 더할 수 있는 모든 경우의 수를 합해줘야 하므로

 

3. dp[x] = dp_1[x] + dp_23[x]   <=  최종적인 답은 dp[x] 가 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int dp[10001], dp_1[10001], dp_23[10001];

void test()
{
	dp[1] = 1, dp[2] = 2, dp[3] = 3;
	dp_1[2] = 1, dp_1[3] = 2;
	dp_23[2] = 1, dp_23[3] = 1; // temporary value
	for (int i = 4; i <= 10000; i++) {
		dp_23[i] = dp_23[i - 2] + (i % 3 == 0 ? 1 : 0);
		dp_1[i] = dp_1[i - 1] + dp_23[i - 1];
		dp[i] = dp_1[i] + dp_23[i];
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	test();

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << dp[n] << endl;
	}

	return 0;
}