[BOJ] 11047번 : 동전 0

1. problem : 

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

 

2. solution1 :

#include <bits/stdc++.h>
using namespace std;
int n, k; 
int coins[12]; 
int d[12]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> k; 
	for (int i = 1; i <= n; i++) cin >> coins[i]; 
	
	for (int i = n; i >= 1; i--) {
		if (k >= coins[i]) {
			int maxcnt = k / coins[i]; 
			k -= maxcnt * coins[i]; 
			d[i] = maxcnt;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (d[i]) ans += d[i];
	}
	cout << ans << '\n';
}

 

 

그리디 알고리즘을 이용해서 풀었다. 문제 풀이를 떠올릴 때, 제일 큰 가치의 동전부터 사용하면 되지 않을까?라는 막연한 생각이 들었고, 그 풀이를 구현하니 운이 좋게 정답을 맞힐 수 있었다. 하지만 , 그리디 알고리즘을 쓸 수 있었던 이유는 다음과 같다. 

 

<귀류법> 보조정리 1. 10/100원짜리는 4개 이하로 사용한다. 50원짜리는 1개 이하로 사용한다. 

보조정리 1을 증명하기 위해, 귀류법을 사용한다. 만약, 10/100원짜리 5개 이상이면, 50/500원으로 대체할 수 있다. 50원짜리 동전 2개 이상이라면 100원짜리로 대체할 수 있다. 이 경우, 5개 이상, 2개 이상 쓰게 될 경우 사용하는 동전의 수가 최소임을 만족하지 못한다.  따라서, 보조정리 1이 참이다. 

 

이 과정을 거치고 난 다음, 동전 0이라는 문제에서 필요한 명제를 보자. 

<명제> 상품을 구매할 때, 500원짜리 동전을 최대한 사용해야, 사용하는 동전의 수가 최소가 된다. 

<증명> 10,50,100원을 보조정리 1을 이용하여 만들 수 있는 최대금액은 490원이다. 이때, 500원을 다 사용하지 않고, 10,50,100원에게 토스할 경우, 490원이 500원 이상을 감당해야 한다. 따라서, 500원짜리는 있는 만큼 다 써야 한다. 

이와 같은 과정을 일반화시키면, 500원을 다 쓰고, 100원을 다 쓰고... 이런 식으로 논리가 전개 가능해진다. 

 

참고한 자료 : https://youtu.be/De0Qg-2O80c?si=WDoMRbzlPnvQRDc5