[BOJ] 11047. 동전 0 (C++)

문제

N종류의 동전을 사용해 K의 값을 만들 때 필요한 동전을 최소화하기

동전의 가치가 오름차순으로 주어진다

생각할 것

가지고 있는 동전을 최소화해야 하므로 큰 단위의 동전을 나눌 수 있는 만큼 최대한 나눈다.

→ 그리디 알고리즘을 이용한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;

    vector<int> vec(N); // 동전 가치
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }

    int coin = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (K >= vec[i]) {
            int tmp = K / vec[i];
            coin += tmp;
            K -= (tmp * vec[i]);
        }
    }

    cout << coin;

    return 0;
}