예제 문제의 C++ 풀이

다음 예제는 가장 적은 동전 개수로 특정 금액을 만드는 문제입니다. 각 동전의 단위가 주어졌을 때, 최소 동전 개수로 목표 금액을 만들기 위해 그리디 알고리즘을 사용할 수 있습니다.

C++ 코드 예제:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int min_coins(int target, vector& coins) {
    sort(coins.rbegin(), coins.rend());  // 큰 단위의 동전부터 사용하기 위해 내림차순 정렬
    int count = 0;

    for (int coin : coins) {
        // 현재 동전으로 만들 수 있는 최대 개수를 계산
        if (target >= coin) {
            count += target / coin;
            target %= coin;  // 남은 금액 계산
        }
    }
    return count;
}

int main() {
    int target = 760;
    vector coins = {500, 100, 50, 10};
    cout << min_coins(target, coins) << endl;  // 출력: 4 (500 + 100 + 100 + 50 + 10)
    return 0;
}
        

설명: 위의 코드는 가장 큰 단위의 동전부터 사용하여 목표 금액을 만드는 방식입니다. 큰 단위의 동전을 우선 사용함으로써 최적의 동전 개수를 빠르게 구할 수 있습니다.