BOJ 11047 - 동전 0 문제풀이

문제를 읽고 이해하기

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 그리고 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

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

재정의와 추상화

2020/03/27 - [알고리즘/문제풀이] - BOJ 2293 - 동전 1 문제풀이

BOJ 2293 - 동전 1 문제풀이

이전에 풀이했던 동전 1 문제를 생각해보자. 동전 1 문제는 주어진 동전을 사용하여 K원을 만들 수 있는 모든 경우의 수를 구하는 문제고, 이 문제는 주어진 동전을 이용하여 K원을 만들 수 있는 경우 중 최소한의 동전을 사용하는 경우에서 사용한 동전의 개수를 구하는 문제이다.

비슷해 보이지만, 근본부터 다른 문제이다. 이 문제는 최솟값이라는 점이 포인트이다. 가장 적은 수의 동전을 사용하려면 주어진 K원보다 작거나 같은 값을 가지는 동전 중에서 가장 큰 값을 가지는 동전부터 차례대로 사용하는 것이다. 따라서 이 문제는 그리디(탐욕법) 알고리즘을 사용한 문제이다.

문제 이해만 하면 코딩은 간단하다. 필자는 우선순위 큐(priority_queue)를 이용하여 큰 값을 가지는 동전부터 사용하도록 구현하였다. (생각해보니 입력이 오름차순으로 주어지니 그냥 배열로 선언해도 될 것 같..네요)

코드 작성

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq;

int main() {
    int count = 0;
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        if (temp <= k)
            pq.push(temp);
    }

    while (k != 0) {
        int now_coin = pq.top();
        if (now_coin > k) {
            pq.pop();
            continue;
        }
        k -= now_coin;
        count++;
    }
    cout << count;
    return 0;
}