동전 2 (feat. 백준, 2294번)

동전 2
https://www.acmicpc.net/problem/2294

2294번: 동전 2

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2293
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, K, arr[101], dp[10001];
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i];
	sort(arr + 1, arr + 1 + N);
	for (register int i = 1; i <= K; ++i)
		dp[i] = static_cast<int>(1e9);
	for (register int i = 1, j; i <= N; ++i)
		for (j = arr[i]; j <= K; ++j)
			if (j % arr[i] == 0)			dp[j] = min(dp[j], j / arr[i]);
			else					dp[j] = min(dp[j], dp[j - arr[i]] + 1);
	if (dp[K] == static_cast<int>(1e9))
		cout << -1 << endl;
	else
		cout << dp[K] << endl;
	return 0;
}
// *&)*@*

N=3, K=5, 동전은 1,2,3 이 있다고 가정해봅니다.

일단 1원으로 1~5원을 만들어보겠습니다. 1원은 1원 1개, 2원은 1원 2개, ..., 5원은 1원 5개가 필요합니다.

1	2	3	4	5
1	2	3	4	5

다음은 2원으로 2~5원을 만들어보겠습니다. 2원은 2원 1개, 3원은 2원 1개 + 1원 1개, 4원은 2원 2개, 5원은 2원 2개 + 1원 1개 가 필요합니다.

1	2	3	4	5
0	1	1 + 1	2	2 + 1

다음은 3원으로 3~5원을 만들어보겠습니다. 3원은 3원 1개, 4원은 3원 1개 + 1원 1개, 5원은 3원 1개 + 2원 1개 가 필요합니다.

1	2	3	4	5
0	0	1	1 + 1	1 + 1

따라서 5원일때 최소가 되는 경우는 3원 1개 + 2원 1개 가 됩니다.

 

다시 2원으로 2~5원을 만드는 경우를 보겠습니다. 2원은 2로 나누어 떨어지므로 2 / 2 = 1개 입니다. 3원은 2로 나누어 떨어지지 않습니다. 1원이 필요로 합니다. 그럼 3원에서 2원을 빼면 1원입니다. 즉, 3원은 2원 한개와 나머지를 1원으로 채웠습니다. 따라서 3원은 2원 + (3원 - 2원) 이 됩니다. 4원은 나누어 떨어지므로 4 / 2 = 2개 입니다.

 

3원으로 3~5원을 만드는 경우를 보겠습니다. 5원은 3원으로 나누어 떨어지지 않습니다. 1원 또는 2원이 필요합니다. 그렇다면 2원은 어떻게 만들어졌나요? 1원 2개 또는 2원 1개 입니다. 이때 최소 필요개수는 2원 1개 입니다. 따라서 5원은 3원 + (5원 - 3원) 이 됩니다.

 

즉, 만들고 싶은 액수에 대해서 내가 가진 동전으로 나누어 떨어진다면 A/B의 개수가 결국 필요한 동전의 개수입니다.

나누어 떨어지지 않는다면 내가 가진 동전(1개) + (만들고 싶은 액수 - 내가 가진 동전) 입니다. 여기서 (만들고 싶은 액수 - 내가 가진 동전) 은 내가 가진 동전보다 이전에 이미 연산된 결과들이고, 이중 최소값을 갖는 값을 계속 취했습니다.