<백준> 11047번 동전 0

문제

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

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

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

문제 해결 과정:

- 내야하는 값보다 작은 값을 지닌 동전을 뺸다

- 뺀값이 빼는 동전값 보다 작아질때까지 빼고 만약 동전값보다 작다면 그 동전값보다 작은 동전값에 대해서 위 과정을 반복한다.

- 우선순위 큐를 사용하여 동전 값중 가장 큰값부터 시작한다.

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
 
 
int main() {
    int N;
    int K;
    int temp;
    int coin;
    int cnt = 0;
 
    priority_queue<int, vector<int>,  less<int> > p;
    
    scanf_s("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        cin >> temp;
        p.push(temp);
    }
 
    while (!p.empty()) {
        coin = p.top();
        while (K >= coin) {
            K -= coin;
            cnt++;
        }
        p.pop();
    }
 
    cout << cnt<<endl;
    return 0;
}