백준 15989 c++ "1, 2, 3 더하기 4" -PlusUltraCode-

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

 

[필자 사고]

늘 더하기 문제는 숫자들의 순서가 상관이 있었다.

다만 이 문제만의 특별한 점은 순서가 상관이 없다.

즉 필자는 몰랐던 개념을 배웠다.

오름차순 느낌으로 점화식을 설계해야 된다.

dp[i][k] i번째 수는 k이하의 수로 완성한다.

 

즉 dp[i][k] = dp[i-k][k--] 이런식으로 값을 덮어 씌어야 된다.

 

이전에 순서가 상관이 있을 때는 값을 += 형태로 더해나가는 동적 프로그래밍이다.

위와 같은 논리를 이해하게 되면 문제를 풀 수 있다.

아래는 자세한 코드 해설입니다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 dp 배열을 초기화하는 역할을 합니다.

• dp 벡터를 크기 10001 × 4로 초기화합니다.
  • dp[i][j]는 숫자 i를 만들 때, 1, 2, 3 중 j를 마지막에 사용한 경우의 수를 저장하는 2차원 벡터입니다.
• 0부터 10000까지의 모든 경우를 처리할 수 있도록 dp 배열을 미리 할당합니다.

---

3. 동적 계획법을 이용한 경우의 수 계산 (Game_Start 함수)

이 함수는 동적 계획법(DP, Dynamic Programming)을 이용하여 1, 2, 3을 사용하여 특정 수를 만드는 방법의 개수를 계산합니다.

1. 기본 초기값 설정
   • dp[1][1] = 1 → 숫자 1은 1만 사용해서 만들 수 있음
   • dp[2][1] = 1, dp[2][2] = 1 → 숫자 2는 1+1 또는 2로 만들 수 있음
   • dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1 → 숫자 3은 1+1+1, 1+2, 3로 만들 수 있음
2. 점화식을 이용한 DP 테이블 채우기
   • dp[i][1] = dp[i-1][1]
     • i-1까지 1을 사용해서 만든 방법을 그대로 유지
   • dp[i][2] = dp[i-2][1] + dp[i-2][2]
     • i-2까지 1과 2를 사용해서 만든 방법에 +2를 추가
   • dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]
     • i-3까지 1, 2, 3을 사용해서 만든 방법에 +3을 추가

이렇게 하면 오름차순을 유지하며 숫자를 조합하는 경우의 수를 정확히 구할 수 있습니다.

---

4. 테스트 케이스 처리 (main 함수)

1. T (테스트 케이스 개수)를 입력받습니다.
2. Input()을 호출하여 DP 배열을 초기화합니다.
3. Game_Start()를 호출하여 DP 테이블을 채웁니다.
4. 각 테스트 케이스마다 N을 입력받고, dp[N][1] + dp[N][2] + dp[N][3]을 출력합니다.
   • 이는 숫자 N을 만들 수 있는 모든 경우의 수를 합산한 결과입니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int T;
int N;
vector<vector<long>> dp;

void Input() {
	dp.resize(10001);
	for (int i = 0; i <= 10000; i++) {
		dp[i].resize(4);
	}
}

void Game_Start() {
	
	dp[1][1] = 1;
	dp[2][1] = 1;
	dp[2][2] = 1;
	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;

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

int main(void) {
	cin >> T;
	Input();
	Game_Start();
	while (T--) {
		cin >> N;
		
		cout << dp[N][1] + dp[N][2] + dp[N][3] << '\n';
	}
}