[C/C++] 가장 작은 개수의 동전으로 n원을 만드는 알고리즘 구현 (greedy)

 

Suppose we want to make change for n won, using the least number of coins of denominations 1, 10, and 25 won. Consider the following greedy strategy: suppose the amount left to change is m. take the largest coin that is no more than m. subtract this coin's value from m, and repeat. Either give a counterexample, to prove that this algorithm can output a non-optimal solution, or prove that this algorithm always outputs an optimal solution.

#include <stdio.h> 
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int changes[] = { 1, 5, 10, 25}; // 잔돈 목록
int n = sizeof(changes) / sizeof(changes[0]); // 배열 원소 개수

void find(int M)
{
    sort(changes, changes + n, greater<int>());
    vector<int> ans;

    for (int i = 0; i < n; i++) {

        while (M >= changes[i]) 
        {
            M -= changes[i];
            ans.push_back(changes[i]);
        }
    }

    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
}

int main()
{
    int n;
    cin >> n;
    cout << "거스름 돈 (" << n << ")원 : ";
    find(n);
    return 0;
}

 

<greedy 알고리즘>

n값이 주어지면 가장 큰 단위인 25원부터 검사하여 현재 돈(M)이 25원보다 크다면 25원보다 작아질 때까지 25라는 값을 벡터 컨테이너에 넣고 M에서 25를 뺀다.
M이 25보다 작을 경우 다음 큰 단위인 10원으로 검사하여 현재 돈(M)이 10원보다 크다면 10원보다 작아질 때까지 10이라는 값을 벡터 컨테이너에 넣고 M에서 10을 뺀다.  
마찬가지로 M이 10보다 작을 경우 다음 큰 단위인 1원으로 검사하여 현재 돈(M)이 1원보다 크다면 1원보다 작아질때까지 1이라는 값을 벡터 컨테이너에 넣고 M에서 1을 뺀다. 

EX) 77원의 경우
1. 77원(M)이 25원보다 크거나 같으므로 벡터 ans에 25를 넣고 M-25를 해준다. (ans = [25])
2. 52원(M)이 25원보다 크거나 같으므로 벡터 ans에 25를 넣고 M-25를 해준다. (ans = [25, 25])
3. 27원(M)이 25원보다 크거나 같으므로 벡터 ans에 25를 넣고 M-25를 해준다. (ans = [25, 25, 25])
4. 2원(M)이 25원보다 작으므로 다음 큰 단위(10원)로 넘어간다.
5. 2원(M)이 10원보다 작으므로  다음 큰 단위(1원)로 넘어간다.
6. 2원(M)이 1원보다 크거나 같으므로 벡터 ans에 1을 넣고 M-1을 해준다. (ans = [25, 25, 25 ,1])
7. 1원(M)이 1원보다 크거나 같으므로 벡터 ans에 1을 넣고 M-1을 해준다. (ans = [25, 25, 25, 1, 1])
8. 0원(M)이 1원보다 작으므로 while문을 탈출하지만 for문의 마지막 회이기 때문에 반복문도 종료된다.

 

그러나 greedy 알고리즘이 항상 최적의 솔루션은 아니다.

예를 들어 동전의 단위가 20,12,1원이 있다고 가정할 때 위와 같은 알고리즘으로 계산 시 
24원 = 20 + 1 + 1 + 1 + 1 로 동전 5개를 소모하지만 가장 최적의 답은 24원 = 12 + 12로 동전 2개를 소모하는 것이다. 동전의 단위가 20, 8 ,1원이 있다고 가정할 때 가장 최적의 답은 24원 = 8 + 8 + 8로 동전 3개를 소모하는 것이다. 이러한 반례에서 보이듯이 탐욕 알고리즘이 항상 최적의 결과를 보이는 것은 아니다. 큰 단위의 동전이 작은 단위의 동전의 배수가 되어야 탐욕 알고리즘을 적용할 수 있다.