[자바] 백준 2720 - 세탁소 사장 동혁 (java)

 문제 : boj2720

---

 

필요 알고리즘 개념

• 그리디
  
  • 매번 최선의 선택을 하면 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제에서 제시하는 화폐의 단위는 큰 것부터 25, 10, 5, 1 센트이다.

매번 남아있는 거스름돈에 대해 줄 수 있는 가장 큰 가치의 화폐를 줄 수 있는 만큼 주면 된다.

 

예를들어 124센트를 봐보자. 

1. 124센트를 가지고 25센트짜리 화폐로 줄 수 있는만큼 주면 124 = 25 x 4 + 24 이므로, 4개를 주고 24센트가 남는다.

2. '1'에서 남은 24센트를 가지고 10센트로 줄 수 있는만큼 주면 24 = 10 x 2 + 4 이므로, 2개를 주고 4센트가 남는다.

3. 남은 4센트에 대해 5센트로는 줄 수 없다. 4 = 5 x 0 + 4

4. 남은 4센트에 대해 1센트로는 4개를 줄 수 있다. 4 = 1 x 4 + 0

 

따라서 답은 '4 2 0 4' 가 된다. 코드에서 '/'는 나눈 몫이고, '%'는 나눈 나머지이다.

 

---

 

코드 : github

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

public class Main {
    private static final int[] coins = {25, 10, 5, 1};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            int remain = Integer.parseInt(br.readLine());
            for (int i = 0; i < coins.length; i++) {
                sb.append(remain/coins[i]).append(' ');
                remain%=coins[i];
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}