[백준 2294] 동전 2

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

---

해설

이 문제는 DP 즉, 다이나믹 프로그래밍 문제이다. ( 그리디로도 해봤지만 풀리지 않았다. )

다이나믹 프로그래밍의 특별한 점은 큰 문제를 작은 문제로 나누어서 구한다는 것이다.

그러므로 작은 문제를 메모를 해가면서 큰 문제의 답을 구할 수 있는 발판을 마련하는 것이 다이나믹 프로그래밍 푸는 방법이다.

 

다이나믹 프로그래밍으로 문제를 푸려면 점화식을 구해야한다.

 

예제를 가지고 설명해보겠다.

 

설명은 대충 n번째 동전으로 k원을 만드는 데 필요한 최소 동전의 개수 구하는 걸 표로 써볼 거다.

 

일단 시작하기 앞서 0원은 어떤 동전이든 0개 필요하니,dp[0~n-1][0] = 0 으로 초기화 시켜놓겠다. 또, dp에서 0번 배열을 제외한 나머지 최소 동전 개수는 알 수없으니 INF(매우 큰 수)로 초기화 시켜놓겠다.

---

먼저, 앞으로 간단하게 해볼 일을 말해보겠다.

 

dp[i-1][j] 와 dp[i][j-coin[i]] 를 비교 해 최솟값을 얻을 것이다.

여기서 coin[i] 는 i번째 동전의 금액이고, dp배열은 i에 j번째 배열에 최솟 값이다.

 

아래 예시를 통해 보자.

---

먼저, 1원부터 살펴보겠다.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원
12원

 

1원으로 1원을 만드는 데 1개, 2원을 만드는 데 2개 ··· 15원을 만드는 데 15개라서 다 써놨다.

간단하게 식으로 정리하면, dp[i][i-coin[i]]+1 이다.

---

다음은 5원이다.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12원

5원으로는 1,2,3,4원을 못 만드니, 1원꺼를 밑으로 내려놨다.

나머지는 위에서 설명한 점화식인 dp[i-1][j] 와 dp[i][j-coin[i]] 를 써주었다.

위 배열([i-1])에서 이 i번째에 j번째 값을 만든 최솟 값과 i번 째 동전을 이용해서 만든 최솟 값을 비교해주는 것이다.

---

다음은 10원이다.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
5원	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
12원	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

12원으로는 1,2,3,4,5,6,7,8,9,10,11원을 못 만드니, 5원꺼를 밑으로 내렸다.

이것 또한 위와 같이 했다.

---

이해가 잘 안될 수있다.

코드를 보고, 천천히 이해해보길 바란다.

 

나는 코드의 편의를 위해 2차원 배열로 짰지만, 1차원 배열로도 충분히 가능하다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 987654321;
int dp[101][10001];
int coin[101];
int main() {
	int n, k; 
    cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> coin[i];
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= k; j++)
			dp[i][j] = INF;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= k; j++) {
			if (j < coin[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = min(dp[i - 1][j], dp[i][j - coin[i]] + 1);
		}
	
    if (dp[n][k] == INF)
		cout << -1 << '\n';
	else
	cout << dp[n][k] << '\n';
}