BOJ 11047 동전0

BOJ 11047 동전 0

문제링크 : <https://www.acmicpc.net/problem/11047

요약

N 개의 종류의 동전이 있고 각 동전은 무수히 많다. 동전을 조합해서 가치의 합을 K로 만들려고 할 때 필요한 동전의 최소 개수를 구하는 문제이다.

풀이

첫 번째 예제 입력값을 보자 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000의 가치를 가진 동전들로 4200원을 만들어야 한다.

이 문제의 풀이법은 생각보다 쉽게 떠올릴 수 있을 것이다. 무조건 사용할 수 있는 범위 내에서 가장 큰 가치를 가진 동전을 많이 사용하는 것이다. 4200원을 만들기 위해서 4200원 이하의 가장 큰 액수가 1000원이므로 4번 사용해서 4000원을 만들 수 있다. 그러면 200원이 남게 되고 그다음으론 100원짜리를 두 번 써서 총 1000 x 4 + 100 x 2로 4200원을 만들 수 있고 답은 6이 된다.

그대로 구현하면 된다.

코드

#include<iostream>
using namespace std;
int n, k, arr[11],cnt;
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		if (arr[i] <= k) {
			cnt += k / arr[i];
			k %= arr[i];
		}
	}
	cout << cnt << "\n";
}