[백준] 5585번 : 거스름돈 – JAVA [자바]

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

---

• 문제

 

 

---

• 문제 풀이

백준 5585번 거스름돈은 브론즈 2 난이도의 그리디 문제이다. 이 문제에서는 가격 N이 주어진다. 그리고 항상 1000엔짜리 지폐로 계산하고 거스름돈은 500엔, 100엔, 50엔, 10엔, 5엔, 1엔으로 받을 수 있다. 이때 최소의 개수로 거스름돈을 받는다고 할 때 받는 거스름돈의 매수를 출력하면 된다.

 

우선 최소의 개수로 거스름돈을 받는다고 하면 우선 가장 큰 금액부터 받으면 된다. 즉, 만약에 거스름돈이 100엔이라고 하면 100엔짜리 1장을 받는 게 1엔짜리 100개를 받는 것보다 낫다. 

 

이 내용을 이용해서 문제에서 주어진 예시를 보겠다.

 

EX 1) 380

가격이 380엔이니까 거스름돈으로 620엔을 받아야 한다. 따라서 500엔짜리 1개, 100엔짜리 1개, 그리고 10엔짜리 2개, 총 4개를 받으면 된다.

 

EX 2) 1

가격이 1엔이니까 거스름돈으로 999엔을 받아야 한다. 따라서, 500엔짜리 1개, 100엔짜리 4개, 50엔짜리 1개, 10엔짜리 4개, 5엔짜리 1개, 1엔짜리 4개를 받으면 된다. 총 15개이다. 

 

이 예시에서 확인을 할 수 있듯이 우선 금액을 입력받으면 거스름돈을 받아야 할 돈을 계산한다. 이 돈을 n이라고 하겠다. 그리고 500, 100, 50, 10, 5, 1엔을 저장하는 배열을 만든다.

 

그리고 가장 큰 500부터 while-loop을 이용해서 n으로 빼준다. 만약에 n - 500이 0 이상이면 빼도 count를 1 증가시켜주고 loop을 계산한다. 만약에 n - 500이 0보다 작으면 다음 거스름돈인 100으로 같은 과정을 거친다.

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = 1000 - Integer.parseInt(br.readLine());  //줘야할 잔돈
        int count = 0;  //잔돈에 포함된 매수
        int[] money = {500, 100, 50, 10, 5, 1};  //잔돈 줄 수 있는 금액들
        int i = 0;
        while (n != 0) {
            if (n - money[i] >= 0) {
                n -= money[i];
                count++;
            } else {
                i++;
            }
        }
        System.out.print(count);
    }
}