[백준/BOJ/C++] 11047번 동전 0 - Greedy

11047번: 동전 0

1. 문제

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

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

---

2. 입력

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

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

---

3. 출력

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

---

4. 풀이

동전의 개수를 최소로 만드려면 동전의 큰 단위를 많이 사용해야한다.

동전의 가장 큰 단위부터 검사해서 입력된 K값보다 단위가 작을 때, 그 K 값을 그 동전 단위로 나눈 몫만큼 카운트에 더해준다. 그리고 K값은 그 동전을 뺀만큼 빼준다.

---

5. 소스코드

#include <iostream>
using namespace std;
int main(){
    int N, K; //N : 동전종류, K : 금액.
    cin>>N>>K;
    int *money = new int[N];

    for(int i = 0; i < N; i++){
        cin>>money[i];
    }

    int count = 0;
    int Q;
    for(int i = N - 1; i >= 0; i--){
        if(K >= money[i]){
            Q = K/money[i];
            count += Q;
            K -= money[i]*Q;
        }
        if(K == 0)
            break;
    }
    cout<<count;
}