[이코테] 그리디 - 거스름돈 - JAVA

💡 문제

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

💬 입출력 예시

입력 : 1260
출력 : 6

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/* 동전 거스름돈 문제 */
public class greedy_01 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] coins = {500, 100, 50, 10};
        int N = Integer.parseInt(br.readLine());
        int answer = 0;
        // 값이 큰 동전부터 거슬러 줌
        for (int coin: coins) {
            answer += N / coin;		// 몫 : 개수
            N %= coin;				// 나머지 : 남은 금액
        }
        System.out.println(answer);
    }
}

📄 해설

• 거슬러 줘야 할 돈 N 은 항상 10의 배수 에 의하여, 그리디 알고리즘을 적용하여 해결하면 되는 문제
• 큰 단위의 돈부터 확인하여 거슬러 주면 해결
• 몫(N / coin) 은 거슬러 준 동전의 개수를 의미하고, 나머지(N % coin) 는 남은 거스름 돈을 의미함