[백준 5585] - [그리디알고리즘] - 거스름돈 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/5585

---

이문제는 어렵지 않은 그리디 알고리즘 문제이다. 

그리디 알고리즘 이란 탐욕적 알고리즘으로 모든 경우의 수를 다 구하면 된다. 

거스름돈을 구하는 경우는 아주 쉬운 예제 인데 접근 법은 남은 잔액에서 금액이 큰 동전부터 지급 가능한 개수를 구해나가면 된다.

예제로 380원이 물건 값이 나왔고 1000엔을 받았을때 620원을 거스름돈으로 지불해야 한다.

지불 할 수 있는 동전은 500, 100, 50, 10, 5, 1 엔 총 6가지의 동전이 존재한다. 

최소의 개수로 거스름돈을 지불 하고자 한다면 금액이 큰 동전 위주로 지불해주면 되기 때문에 금액이 큰 500엔 부터 줄 수 있는 경우의 수를 구한다.

1)    500엔 으로 지불 가능한 개수 

현재 잔돈 620 원에 500엔 하나를 지불할 수 있다.

지불 동전 개수 : 500엔 1개

남은 잔돈 : 120엔

2)   100엔 으로 지불 가능한 개수

현재 잔돈 120엔에 100엔 하나를 지불 할 수 있다.

지불 동전 개수 : 500엔 1개, 100엔 1개

남은 잔돈 : 20엔

3)   50엔 으로  지불 가능한 개수

현재 잔돈 20엔에 50엔으로는 지불 할수 없다.

지불 동전 개수 : 500엔 1개, 100엔 1개

남은 잔돈 : 20엔

4)   10엔 으로 지불 가능한 개수

현재 잔돈 20엔에 10엔으로 2개 지불할 수 있다.

지불 동전 개수 : 500엔 1개, 100엔 1개, 10엔 2개

남은 잔돈 : 0엔

5)   5엔 으로 지불 가능한 개수

현재 잔돈은 0엔이다

지불 동전 개수 : 500엔 1개, 100엔 1개, 10엔 2개

남은 잔돈 : 0엔

6)   1엔 으로 지불 가능한 개수

현재 잔돈은 0엔이다

지불 동전 개수 : 500엔 1개, 100엔 1개, 10엔 2개

남은 잔돈 : 0엔

위의 경우의 수 전부를 소스로 작성하면 된다.

소스

import java.util.Scanner;
 
public class Main {
    public static int price;
    public static int count;
    
    public static int[] coinArr = {500, 100, 50, 10, 5, 1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        price = 1000 - sc.nextInt();
 
        for(int coin:coinArr) {
            getCount(coin);
        }
        
        System.out.println(count);
    }
    
    public static void getCount(int coin) {
        count += (price / coin);
        price = price - (coin * (price / coin));
    }
}