문제

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

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

입력

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

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

출력

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

---

1. 해결방법 및 소스코드

• 최대 힙을 기반으로 한 우선순위 큐(Priority Queue)를 이용하였다.
• 금액이 큰 동전을 우선적으로 더 많이 써야 최종적으로 필요한 동전의 수가 최소가 되기 때문이다.
• 당연히 K원보다 큰 동전은 쓸 수 없으므로 if문에서 검사하여 pop해주고, else문에서는 남은금액과 result값을 업데이트해준다.

#include <iostream> #include <queue> using namespace std; int main() { int N, K, A; int result = 0; priority_queue<int, vector<int>, less<int>> coins; scanf("%d %d", &N, &K); // N개의 코인을 우선순위 큐에 넣는다. for (int i = 0; i < N; i++) { scanf("%d", &A); coins.push(A); } for (int i = 0; i < N; i++) { if (coins.top() > K) { coins.pop(); continue; } else { int num = K / coins.top(); K = K - num * coins.top(); result += num; coins.pop(); } } printf("%d\n", result); }