백준 2225번 합분해

🔒[문제 url]

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

🔑알고리즘

• k개의 동전을 사용하여 n원을 만든다.
  - 그렇다면, 더 적은 수의 동전을 사용해 n원을 만드는 것이라던가, 같은 수의 동전을 사용하지만 n원보다 작게 만드는 경우의 수가 영향을 주지않을까? ==> Dynamic Programming
  
  점화식을 찾기 위해 간단한 예시를 확인해보자.
• 3개의 동전으로 2원을 만든다고 가정하자.
  경우의 수는 2 0 0 0 2 0 1 1 0 1 0 1 0 1 1 0 0 2로 6가지다.
  6가지 경우의 수를 어떻게 이전 값에서 도출할 수 있을까?
  - 2개의 동전으로 2원을 만드는 경우를 살펴보자.
  2 0 0 2 1 1로 3가지인데, 여기서 동전을 하나씩 추가하여 2원을 만들 수는 없을까?
  - 0원을 추가해주면 3개의 동전으로 2원을 만들 수 있게된다.
  ==> 2 0 0 0 2 0 1 1 0
  
  
  - 3개의 동전으로 1원을 만드는 경우를 살펴보자.
  1 0 0 0 1 0 0 0 1로 3가지인데, 2원으로 만들고싶으면?
  - 각 경우의 수에 1원씩 더해주면 된다.
  ==> 1 0 1 0 1 1 0 0 2
  
  
• 아하, 그렇다면 점화식은
  (k개로 n원 만드는 경우의 수) = (k - 1개로 n원 만드는 경우의 수) + (k개로 n - 1원 만드는 경우의 수)가 되는구나!
  
  
  dp[k][n] = dp[k - 1][n] + dp[k][n - 1];
  ==> dp : k원으로 n원을 만드는 방법의 수

🐾부분 코드

// 초기 작업
	
// 0개로 i원을 만드는 경우의 수는 0 (0원 제외)
for (int i = 0; i <= n; i++) dp[0][i] = 0;
// i개로 0원을 만드는 경우의 수는 1 (0을 i개 더함)
for (int i = 0; i <= k; i++) dp[i][0] = 1;

<dp 배열 초기화 부분>
Bottom Up방식을 위한 초기화를 진행한다.

• 0개로 i원을 만드는 경우의 수는, 0원을 제외(0원은 만들 수 있으므로 1) 하고 0이다.
  
  
• i개로 0원을 만드는 경우의 수는, 0원을 i개 사용하면 되므로 1이다.

//Bottom Up Dynamic Programming
for (int i = 1; i <= k; i++)
	for (int j = 1; j <= n; j++)
		dp[i][j] = (dp[i - 1][j] % MOD + dp[i][j - 1] % MOD) % MOD;
        
// Output    
cout << dp[k][n] % MOD;

<dp 진행 및 출력 부분>
MOD는 매크로 변수로 선언해준 1,000,000,000이다.
연산 중 overflow가 발생할 수 있으므로 매번 나머지 연산을 해준다.
점화식은 위에서 설명한대로 적용한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
using namespace std;

#define MOD 1'000'000'000
int n, k;
long long dp[201][201]; // [x][y] : x개로 y원을 만드는 경우의 수

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
}

void SOLVE()
{
	// 초기 작업
	
	// 0개로 i원을 만드는 경우의 수는 0 (0원 제외)
	for (int i = 0; i <= n; i++) dp[0][i] = 0;
	// i개로 0원을 만드는 경우의 수는 1 (0을 i개 더함)
	for (int i = 0; i <= k; i++) dp[i][0] = 1;

	//Bottom Up Dynamic Programming
	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = (dp[i - 1][j] % MOD + dp[i][j - 1] % MOD) % MOD;
	cout << dp[k][n] % MOD;
}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

사실 점화식을 이해하지 못한채 노가다로 배열을 채우다가 확신이 들어 제출했더니, 다행이도 정답이 나와 그제서야 점화식을 이해했다.
연습이 부족한건지, 두뇌 회전이 좀 딸리는건지😥는 모르겠지만,
그래도 아무 도움없이 점화식을 이해했다는 점이 뿌듯했다.
골드 이상의 DP문제를 만나면 점화식을 찾기가 보통 쉽지가 않다. 사실 실버1도.. 그렇지만 누군가는 쉽게 해내기에 나도 할 수 있다는 생각으로 그저 끝없이 도전 또 도전..