백준 2225 c++ "합분해" -PlusUltraCode-

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

 

[필자 사고]

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

이 문제를 해결하기 위해서는 일단 해봐야 된다.

종이를 가져와서 N= 1 일때 K=1일때 갯수 N , K (1, 2) 일때 갯수 ----

계속 해 나아가면 규칙성을 발견할 수 있다.

dp[i][k] = dp[i-1][k] + dp[i][k-1] 의 점화식을 세울 수 있다.

 

역시 동적프로그래밍 문제는 직접 종이들고 경우의수를 만들어야 한다는걸 느낀 문제이다.

 

이래는 자세한 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 사용자로부터 두 개의 정수 NNN과 KKK를 입력받고, 이를 바탕으로 2차원 dp 벡터를 초기화하는 역할을 한다.

• dp 벡터는 크기가 (N+1)×(K+1)(N+1) \times (K+1)(N+1)×(K+1)인 2차원 배열로, dp[i][k]는 "정수 iii를 kkk개의 숫자로 만들 수 있는 방법의 수"를 저장한다.
• 동적 배열을 사용하여 dpdpdp 벡터를 동적으로 크기 조정한다.

---

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

이 함수는 DP를 활용하여 가능한 경우의 수를 계산한다.

(1) 초기화 과정

• dp[1][0] = 0, dp[0][1] = 0, dp[0][0] = 0으로 설정
  • 의미: 0을 1개의 숫자로 만드는 경우를 특별히 다루지 않고, 이후 로직에서 0을 고려하도록 한다.
• dp[1][i] = dp[1][i - 1] + 1
  • 의미: 1을 만들 때는 모든 경우가 1로 채워지므로, iii개의 숫자로 만들 수 있는 방법은 iii개가 된다.
• dp[i][1] = 1
  • 의미: 어떤 정수 iii도 단 하나의 숫자만 사용할 경우 오직 한 가지 방법만 가능하다.

(2) DP 점화식 적용

• dp[i][k] = dp[i - 1][k] + dp[i][k - 1]
  • 의미:
    1. dp[i - 1][k]: 숫자i−1을 k개의 숫자로 만들 수 있는 경우의 수를 그대로 가져옴.
    2. dp[i][k - 1]: 숫자 i를 k−1개의 숫자로 만들 수 있는 경우의 수를 가져와서 한 숫자를 추가하는 방식.
  • 따라서, dp[i][k]는 이전 숫자를 활용한 경우의 수와 이전 횟수(개수)를 활용한 경우의 수를 더한 값이다.

(3) 나머지 연산 적용

• dp[i][k] %= MOD
  • 값이 너무 커지는 것을 방지하기 위해 10910^9109로 나눈다.

---

3. 결과 출력

마지막으로 cout << dp[N][K];를 통해, 정수 NNN을 KKK개의 숫자로 만들 수 있는 모든 경우의 수를 출력한다.

---

시간 복잡도 분석

이 코드의 시간 복잡도는 **O(N × K)**이다.

• 두 개의 중첩된 for문이 있으며, 각각 최대 NNN과 KKK까지 반복하므로 O(N × K) 연산이 발생한다.
• 이는 충분히 효율적인 방법이며, N,K≤200N, K \leq 200N,K≤200 정도의 범위라면 문제없이 동작할 것이다.

[소스 코드]

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

int N, K;
vector<vector<long>> dp;

void Input() {
	cin >> N >> K;
	dp.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		dp[i].resize(K + 1);
	}
}

void Game_Start() {
	dp[1][0] = 0;
	dp[0][1] = 0;
	dp[0][0] = 0;
	for (int i = 1; i <= K; i++) {
		dp[1][i] = dp[1][i - 1] + 1;
	}
	for (int i = 1; i <= N; i++) {
		dp[i][1] = 1;
	}

	for (int i = 2; i <= N; i++) {
		for (int k = 2; k <= K; k++) {
			dp[i][k] = dp[i - 1][k] + dp[i][k - 1];
			dp[i][k] %= MOD;
		}
	}

	cout << dp[N][K];
}

int main(void) {
	Input();
	Game_Start();
}