[SWEA]1970. 쉬운 거스름돈 java

그리디문제!

화폐 단위는 정해져있기에 먼저 내림차순으로 배열을 만든다.

큰 값부터 나눠줄 수 있으면 나눈 후 몫을 저장하고, 화폐 단위를 바꿔준다.

현재 값이 0이 될 때까지 반복한다.

 

구현 코드

import java.util.*;
import java.io.*;
 
class Solution {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T;
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
        int[] money = { 50000, 10000, 5000, 1000, 500, 100, 50, 10 };
        StringBuffer sb = new StringBuffer();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int change = Integer.parseInt(st.nextToken());
            int[] answer = new int[8];
 
            for (int i = 0; i < money.length; i++) {
                int cur = change/money[i];
                change %= money[i];
                answer[i] = cur;
            }
 
            sb.append("#" + test_case + "\n");
            for(int x : answer) sb.append(x + " ");
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
}