Greedy-거스름돈

문제

• 책, ‘이것이 취업을 위한 코딩 테스트다’ / ch3 Greedy / 예제 3-1 (p.87)

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.

Step 1. 문제 접근

이 문제는 가장 적은 갯수의 동전으로 손님에게 거슬러 줘야하므로, 최대한 큰 단위의 동전들로 거스름돈 액수를 구성해야한다.

즉, 가장 큰 화폐 단위부터 돈을 거슬러 준다.

Step 2. 선택한 알고리즘

Greedy 알고리즘

• Greedy (탐욕법)

  현재 상황(고려하는 turn)에서 당장 좋은 것만 고르는 방법 (이후는 고려하지 )

Step 3. 선택 이유

가장 큰 화폐부터 고려한다고 가정했을 때(turn), 해당 차례에 동전을 가장 많이 사용하는 것이 궁극적으로 최적의 해가 된다.

그 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

즉, 화폐의 종류가 K개라고 할 때, 코드의 시간 복잡도는 O(K).

※ 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관

Step 4. 구현 (코드)

public class 거스름돈문제 {
    
    public static void main(String[] args) {    
        int n = 1260 ; // 손님에게 건네줘야할 거스름돈 
        int cnt = 0 ; // 거스름돈 구성 동전 개수 
        int[] coinTypes = {50, 10, 500, 100} ; 
        
        Arrays.sort(coinTypes) ; // 코인 종류를 큰 순서대로 정렬 
        
        for(int coin : coinTypes) { // 코인 종류를 큰 순서대로 하나씩 고려하면서 
            cnt += n/coin ; // 해당 코인으로 거슬러 줄 수 있는 동전 갯수 누적 
            n %= coin ; // 나머지를 다음 for문으로 넘겨서 다음 동전 갯수 구하기   
        } // for 
        System.out.println(cnt);
    } // main
} // class 
​