백준 15990 c++ "1, 2, 3 더하기 5" -PlusUltraCode-

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

 

[필자 사고]

동적 프로그래밍 문제이다.

처음 이 문제를 봤을 때 당황했던 점은 연속된 수는 불가능 하다는 점이다.

연속된 숫자가 가능하면 동적프로그래밍 계단 문제와 비슷한 알고리즘으로 풀 수 있는데 아쉬웠다.

그런 다음 생각한 사고 방식이 이전에 사용한 숫자를 기록할 수단이 필요 했다는 점이다.

그래서 필자는 2차원 방식을 생각을 했고 DP[N][3] 식으로 1,2,3을 닮을 공간을 마련해줬다.

그런 다음 점화식은 dp[i][1]  = dp[i-1][2] + dp[i-1][3] 형태로 구현했다. 현재 1이라는 숫자를 넣을거니깐 

i-1칸으로 간뒤 이전값이 2와 3인 dp들의 값을 더하는 방식이다.

위와 같은방법을 1,2,3을 반복하면 해당 문제를 풀 수 있다.

 

[코드 해설]

2. 배열 초기화

프로그램에서는 2단계의 배열 초기화를 수행한다.

첫 번째 단계는 Init_Arr 함수에서 이루어진다. 이 함수는 dp 벡터를 초기화하고, 크기를 100001로 설정한 뒤, 각 인덱스마다 1부터 3까지의 값을 저장할 수 있도록 내부 배열을 4칸으로 설정한다.

두 번째 단계는 Init_Dp 함수에서 이루어진다. 여기서 dp 배열의 초깃값을 설정한다.

• dp[1]은 숫자 1을 만들 수 있는 경우로, 마지막에 1을 사용한 경우만 가능하므로 dp[1][1] = 1이다.
• dp[2]는 숫자 2를 만들 수 있는 경우로, 마지막에 2를 사용한 경우만 가능하므로 dp[2][2] = 1이다.
• dp[3]은 숫자 3을 만들 수 있는 경우로, 마지막에 1, 2, 3을 사용한 경우 모두 가능하여 dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1이 된다.
• dp[4]는 숫자 4를 만들 수 있는 경우로, 마지막에 1을 사용한 경우(3+1), 마지막에 3을 사용한 경우(1+3)만 가능하여 dp[4][1] = 2, dp[4][3] = 1이다.

---

3. 동적 계획법을 활용한 결과 계산

Game_Start 함수에서는 dp 배열을 미리 계산하여 빠른 답변을 제공할 수 있도록 한다.

이 과정에서 숫자 iii를 만들기 위해 마지막으로 사용한 숫자에 따라 값을 계산한다.

• 마지막 숫자가 1일 경우, 이전 숫자가 2 또는 3이어야 하므로 dp[i][1] = dp[i-1][2] + dp[i-1][3]
• 마지막 숫자가 2일 경우, 이전 숫자가 1 또는 3이어야 하므로 dp[i][2] = dp[i-2][1] + dp[i-2][3]
• 마지막 숫자가 3일 경우, 이전 숫자가 1 또는 2이어야 하므로 dp[i][3] = dp[i-3][1] + dp[i-3][2]

각 단계마다 결과 값을 나머지 연산을 적용하여 오버플로우를 방지한다.

---

4. 입력 처리 및 결과 출력

프로그램은 먼저 T개의 테스트 케이스를 입력받는다.
각 테스트 케이스마다 숫자 NNN을 입력받고, 미리 계산된 dp[N] 값을 활용하여 결과를 출력한다.
결과 값은 dp[N][1] + dp[N][2] + dp[N][3]의 합이며, 이를 MOD = 1000000009로 나눈 나머지를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MOD 1000000009
using namespace std;

int N;
vector<vector<long>> dp;
void Init_Dp() {
	dp[1][1] = 1;
	dp[1][2] = 0;
	dp[1][3] = 0;
	dp[2][1] = 0;
	dp[2][2] = 1;
	dp[2][3] = 0;
	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;
	dp[4][1] = 2;
	dp[4][2] = 0;
	dp[4][3] = 1;
}
void Init_Arr() {
	dp.clear();
	dp.resize(100001);
	for (int i = 0; i <= 100001; i++) {
		dp[i].resize(4);
	}
}
void setDivision(int i,int k) {
	dp[i][k] %= MOD;
}
void getResultCount(int idx) {
	long resultCount = 0;

	for (int k = 1; k <= 3; k++) {
		resultCount += dp[idx][k];
		resultCount %= MOD;
	}
	
	cout << resultCount << '\n';
}
void Game_Start() {
	
	Init_Arr();
	Init_Dp();

	for (int i = 4; i <= 100000; i++) {
		dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
		dp[i][2] = dp[i - 2][1] + dp[i - 2][3];
		dp[i][3] = dp[i - 3][1] + dp[i - 3][2];
		setDivision(i, 1);
		setDivision(i, 2);
		setDivision(i, 3);
	}
}

int main(void) {
	int T;
	cin >> T;
	Game_Start();
	while (T--) {
		int num;
		cin >> num;
		getResultCount(num);
	}
}