[백준 11047] 동전0 (C++)

📕문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

💡문제 해석

전형적인 탐욕 법 문제이다.

N개의 동전을 이용해서 k원을 만들면 되는데 최소한의 동전을 사용해야 한다.

그러면 항상 최선의 선택(여기서는 가장 큰 가치의 동전)을 하면 된다.

 

구현

1. 동전을 입력받고 내림차순으로 정렬하기.

2.k원과 coin을 비교해서 넣어주기.

• 만약 coin [i]가 k보다 크다면 진행할 이유가 없다.
• 만약 작다면 그 동전으로 k원을 만들 수 있는 최대의 개수를 뽑고 동전을 사용했으니 사용한 만큼 k원을 다시 최신화해주면 된다.

3. 동전의 개수 구하기

• answer 배열에 모든 원소를 더하면 그 값이 동전의 개수이다.

📜코드

//백준 11047 동전0 실버4
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
vector<int> answer;
bool comp(int a, int b)
{
    return a > b;
}
int main()
{
    cin >> n >> k;
    vector<int> coin(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }
    sort(coin.begin(), coin.end(), comp);
    for (int i = 0; i < n; i++)
    {
        if (coin[i] > k)
        {
            continue;
        }
        else
        {
            answer.push_back(k / coin[i]);
            k = k - answer.back() * coin[i];
        }
    }
    int sum = 0;
    for (auto a : answer)
    {
        sum += a;
    }
    cout << sum;
}

---

✔느낀 점

• 처음 탐욕 알고리즘을 배울 때 예시로 들었던 문제이다.
• 전형적인 탐욕 문제이며 탐욕에 대해 감을 잡을 때 처음 풀면 좋을 문제이다.