[11047] 동전0

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

분류 : 그리디

백준 11047 동전0

동전을 N종류 가지고 있을 때 K원을 만드는 최소 동전의 개수

---

아무런 조건이 없다고 가정할 때, 큰 것 부터 골라야 최소를 만들 수 있을까?

다음의 예를 보자. 우리는 다음 주어진 가격의 동전을 가지고 있다고 하자.

10, 50, 60

100원을 만드려고 그리디하게 구하면 60,10,10,10,10이 나오는데

실제로 100원을 만드는 최소는 50,50이다.

즉, 무조건 큰 것 부터 고르면 안된다는 말이 된다.

그렇다면 어떻게 그리디하게 동전의 최소 갯수를 만들 수 있을까?

다시 예로 돌아가 보자.

5, 40, 70

으로 120원을 만들 경우 70, 40, 5, 5 또는 40, 40, 40이 된다.

이 약수로 부터 얻어지는 조합을 선택하는 것이 무조건 그리디 하게 고르는 것 보다

더 이득을 볼 수도 있다는 말이다.

따라서 이런 경우를 모두 고려하여 최소 갯수를 구해야 한다. (그리디가 답을 보장하지 못한다.)

그런데 이 문제의 경우 입력에 조건이 주어져 있다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

이 조건은 위와 같은 상황이 일어 나지 않는 다는 것이다.

Ai로 만들어 지는 조합은 Ai-1로 만들 경우 무조건 경우의 수가 더 많아 지기 떄문이다.

즉, 이 문제는 그냥 그리디하게 풀면 된다.

코드는 다음과 같다.

#include<iostream>
#include<vector>
using namespace std;
 
int main() {
    int N, K, count=0;
    vector<int> arr;
    cin >> N >> K;
    while (N--) {
        int element; cin >> element;
        arr.push_back(element);
    }
    while (K) {
        int cost = arr.back();
        if (K >= cost){
            int cnt = K / cost;
            K -= (cnt*cost);
            count += cnt;
        }
        arr.pop_back();
    }
    cout << count << '\n';
}