[C++][BEAKJOON][DP] 동전1

[문제]

2293번: 동전 1

 

[문제설명]
n가지의 동전이 있을 때, 이 동전들을 적당히 합쳐서 k원이 되게 하는 경우의 수를 찾는 것.

 

[풀이]
Bottom-up 방식으로 1을 만드는 방법, 2를 만드는 방법, 3을 만드는 방법, ... 10을 만드는 방법까지 구할 것이다.
이 때, 2,3,...을 만드는 방법을 이전에 구한 값을 이용할 것이다.

문제에서 주어진 1,2,5 동전으로 생각해보면,
1,2,5로 1을 만드는 경우의 수는 1 한가지이다.
1,2,5로 2를 만드는 경우의 수는 1+1, 2로 두가지이다.
1,2,5로 3을 만드는 경우의 수는 1+1+1, 1+2로 두가지이다.
1,2,5로 4를 만드는 경우의 수는 1+1+1+1, 1+1+2, 2+2로 세가지이다.
1,2,5로 5를 만드는 경우의 수는 1+1+1+1+1, 1+1+1+2, 1+2+2, 5로 네가지이다.
...

위 경우의 수를 자세히 보면, 1로 만든 경우의 수는 1~5까지의 수가 모두 포함하고 있다.
그리고 1~5 중에 2가 포함될 수 있는 경우에 2를 포함시켜서 만들었고,
1~5 중에 5가 포함될 수 있는 경우에 5를 포함시켜서 만들 수 있다.

즉 1원으로 만들 수 있는 경우를 먼저 더하고
DP[1] = 1 (1)
DP[2] = 1 (11)
DP[3] = 1 (111)
DP[4] = 1 (1111)
DP[5] = 1 (11111)

2원을 추가해서 만들 수 있는 경우를 구해서 더하고
DP[1] = 1 (1)
DP[2] = 1+1 (11,2)
DP[3] = 1+DP[1] = 2 (111,12)
DP[4] = 1+DP[2] = 3 (1111,112,22)
DP[5] = 1+DP[3] = 3 (11111,1112,122)

5원을 추가해서 만들수 있는 경우의 수를 구해서 더하면 된다.
DP[1] = 1 (1)
DP[2] = 2 (11,2)
DP[3] = 2 (111,12)
DP[4] = 3 (1111,112,22)
DP[5] = 3+1 = 4 (11111,1112,122,5)

이 내용을 점화식으로 나타내면 다음과 같다.

dp[x] = y; // y는 주어진 동전들로 x를 만들 때의 경우의 수를 뜻함.
dp[1] = 1 (1)
dp[2] = 2 (1+1, 2)
dp[3] = 2 (1+1+1, 1+2)
dp[4] = 3 (1+1+1+1, 1+1+2, 2+2)
dp[5] = 4 (1+1+1+1+1, 1+1+1+2, 1+2+2, 5)
...

dp[0] = 1;
for (int coin_idx = 0; coin_idx < coin_num; coin_idx++) { //1,2,5
   for (int i = 1; i <= value; i++) { //1~10
     if (i - coins[coin_idx] >= 0) {//1-1 >=0, 2-1>=0, 2-2>=0, 3-1>=0, 3-2>=0, 4-1>=0, 4-2>=0
       dp[i] += dp[i - coins[coin_idx]];
     }
}


참고로 예전에 '1로 만들기'라는 문제에서 2 -> 1로 3 -> 1로 4 -> 1로 만드는 과정을 구한 적이 있다.
이 때도 앞에서 구한 값을 이용해서 bottom-up 방식으로 구했었다.
그 방법은 문제에서 주어진 값을 1로 만들 때, 2로 나누기, 3으로 나누기, 1빼기 의 3가지 방식 중에 가능한 하나를 택하는 것을 반복했다.

for (int i = 2; i <= num; i++) {
   minCountArr[i] = minCountArr[i - 1] + 1;
   if (i % 2 == 0) minCountArr[i] = min(minCountArr[i / 2] + 1, minCountArr[i]);
   if (i % 3 == 0) minCountArr[i] = min(minCountArr[i / 3] + 1, minCountArr[i]);
}

동전문제는 1로 만들기와 유사한 문제라 할 수 있다.

 

 

[코드]

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int coin_num, value; //1 ≤ coin_num ≤ 100, 1 ≤ value ≤ 10,000
	vector<int> coins;

	cin >> coin_num >> value;
	for (int i = 0; i < coin_num; i++) {
		int coin;
		cin >> coin;
		coins.push_back(coin);
	}

	int *dp = new int[value + 1]();
	dp[0] = 1;
	for (int coin_idx = 0; coin_idx < coin_num; coin_idx++) { //1,2,5
		for (int i = 1; i <= value; i++) { //1~10
			if (i - coins[coin_idx] >= 0) {
				dp[i] += dp[i - coins[coin_idx]];
			}
		}
	}
	cout << dp[value] << "\n";

	delete[] dp;
	return 0;
}