[백준] 11047 동전 0 wtih C++

문제설명

---

입출력 예제

---

개념

　K원을 만드는데 필요한 최소한의 동전 개수를 구하는 문제다. 가장 가치가 큰 동전부터 사용하는 것이 최선의 서택이므로, 이러한 선택을 통해 가장 적은 동전을 사용하여 주어진 금액을 만들 수 있는 최적의 해답을 찾을 수 있다. 즉, 그리디 알고리즘을 사용하여 문제를 효율적으로 풀 수 있다.

---

풀이

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

int main()
{
    int N, K, n, answer = 0;
    cin >> N >> K;
    vector<int> v(N);

    for (int i = 0; i < N; ++i)
        cin >> v[i];

    for (auto it = v.rbegin(); it != v.rend(); ++it)
    {
        if (*it < K)
        {
            answer += K / *it;
            K %= *it;
        }
    }

    cout << answer;
}