BOJ 11047 - 동전 0

문제 링크

문제#

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 $N$개의 줄에 동전의 가치 $A_i$가 오름차순으로 주어진다. $(1 \le A_i \le 1{,}000{,}000,\ A_1 = 1,\ i \ge 2$인 경우에 $A_i$는 $A_{i-1}$의 배수$)$

출력#

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

풀이#

동전 가치가 특별한 구조를 가지기 때문에 큰 동전부터 최대한 많이 쓰는 그리디가 통한다. 남은 금액을 현재 동전으로 나눌 수 있는 만큼 나누고, 나머지를 다음 동전으로 넘기면 된다.

코드에서도 동전을 큰 값부터 보면서 사용 개수를 더한다. 한번 큰 동전을 선택해도 손해가 나지 않기 때문에 되돌아갈 필요가 없다.

핵심은 모든 동전 문제에 그리디가 되는 것이 아니라, 이 문제의 동전 체계에서는 그 선택이 항상 안전하다는 점이다.

코드#

#include <iostream>
using namespace std;
 
void solve() {
	int n, k, answer = 0;
	cin >> n >> k;
	
	int money[11] = {};
	for (int i = 0; i < n; i++)
		cin >> money[i];
 
	for (int j = n - 1; j >= 0; j--) {
		if (k == 0)
			break;
 
		answer += k / money[j];
		k %= money[j];
	}
 
	cout << answer << '\n';
	
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 동전을 큰 값부터 한 번씩 확인하므로 $O(N)$이다.
• 공간 복잡도: 동전 배열을 저장하므로 $O(N)$이다.

마무리#

동전 체계가 그리디에 맞춰져 있어서 큰 동전부터 고르는 선택이 그대로 최적해가 된다.