거스름돈 알고리즘(Coin Change Algorithm), 동전교환 알고리즘

그림1. 동전

[출처] https://www.amazon.com/School-Smart-Assorted-Plastic-Coins/dp/B00JKIEQPS 

 

거스름돈 알고리즘(Coin Change Algorithm) 또는 동전교환 알고리즘은 동전 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000}이 있고 값 V 가 주어졌을 때  V와 동일하도록 동전을 선택하는 문제인데 이때 동전의 개수를 최소화(minimum)하는 방법을 찾는 것이다.

(단, 같은 동전을 여러번 선택 가능하다)

예를들어 coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000} 들이 있을때 선택한 동전의 개수는 최소화 하면서 동전의 합이 70원이 되도록 해야만 한다면 20원, 50원 동전 2개를 선택하면 되고 121원이라면 100원, 20원, 1원을 선택하면 해결되는 것이다.

이 문제는 심플한 그리디 알고리즘인데 가능한 가장 큰 동전에서 시작하여 지금까지 선택한 동전의 총합이 거슬러줘야할 돈보다 부족하다면 차이가 0이 될때까지 계속 추가해주면 된다. 

 

 

거스름돈 그리디 알고리즘 순서

1. 선택한 동전의 결과를 저장할 배열을 초기화 한다.
2. V보다 작은 동전중에서 가장 큰 동전을 찾는다. 
3. 발견된 동전을 결과에 추가한다. 그리고 추가한 동전의 금액을 V에서 차감한다
4. V가 0 이 되면 결과를 리턴하고 그렇지 않으면  V의 새 값에 대해 2 단계와 3 단계를 반복한다.

 

 
import java.util.ArrayList;
import java.util.List;
 
public class HelloWorld {
 
 
    public static void main(String[] args) {
 
        int V = 93;
        int coins[] = { 1, 2, 5, 10, 20, 50, 100, 500, 1000 };
        List<Integer> result = coinChangeAlgorithm(coins, V);
        System.out.println(result);
    }
 
 
    public static List<Integer> coinChangeAlgorithm(int coins[], int V) {
 
        int remainingV = V ;
        // 1.선택한 동전의 결과를 저장할 배열을 초기화 한다.
        List<Integer> result = new ArrayList<>();
 
 
        for(int i = coins.length - 1; i >= 0 ; i--) {
            // 2. V보다 작은 동전중에서 가장 큰 동전을 찾는다.
            while(coins[i] <= remainingV) {
                result.add(coins[i]);
                remainingV -= coins[i];
                if(remainingV == 0) {
                    break;
                }
            }
        }
 
        return result;
    }
 
}