[Java] 백준(브론즈-2) 5585번 - 거스름돈

문제 풀이

---

이 문제는 그리디 알고리즘를 이용해 푸는 대표적인 문제이다.

아이디어 도출

이 문제를 풀 수 있는 솔루션은 다음과 같다.

1. 500, 100, 50, 10, 5, 1엔으로 이루어진 동전 목록을 선언한다.
2. 타로가 지불할 돈인 입력 값을 1000에서 뺄셈하여 반환할 거스름돈을 구한다.
3. 500엔부터 1엔까지 순서대로 동전 목록을 순회하며 해당 동전으로 거스름돈을 나눈 몫이 동전 개수가 된다.
4. 동전 개수를 구할 때마다 거스름돈을 빼주고, 총 동전개수에 더해준다.

500엔부터 1엔까지 내림차순으로 순회하는 이유는 거스름돈 동전 개수를 최소화하기 위함이다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    


    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 거스름돈으로 반환할 500, 100, 50, 10, 5, 1엔 동전 목록
        ArrayList<Integer> coinList= new ArrayList<>();
        coinList.add(500);
        coinList.add(100);
        coinList.add(50);
        coinList.add(10);
        coinList.add(5);
        coinList.add(1);

        // 입력한 가격을 1000원에서 뺄셈하여 거스름돈 준비
        int price = 1000 -Integer.parseInt(br.readLine());
        
        // 거스름돈으로 반환할 모든 동전의 개수
        int totalCoinCnt = 0;

        /**
         * 동전 목록을 순회하며 거스름돈으로 줄 동전의 개수를 구한다.
         */
        for(int i=0; i<coinList.size(); i++) {
            int coinCnt = price / coinList.get(i);
            price -= coinCnt * coinList.get(i);
            totalCoinCnt += coinCnt;
        }
        
        bw.write(totalCoinCnt+"\n");
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.