백준 5855번 거스름돈

5855번 거스름돈

문제

난이도

• Bronze2

알고리즘 분류

• 그리디 알고리즘

풀이

public class Main {

    static final int Money = 1000;
    static int[] change = { 500, 100, 50, 10, 5, 1 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int input = Integer.parseInt(br.readLine());
        int n = Money - input;
        int cnt = 0;

        for (int i = 0; i < change.length; i++) {
            int temp = n / change[i];
            if (temp >= 1) {
                cnt += temp;
                n -= change[i] * temp;
            }
        }
        bw.write(cnt + "");
        bw.close();
    }
}

Github

link