[백준] 5585 거스름돈 - Greedy / Java

• 문제 링크

5585번: 거스름돈

 

• 풀이 과정

주어진 동전의 큰 값부터 입력값 n로 나눌 수 있다면,

해당 몫을 res 변수에 누적하고 n 은 그 나머지로 갱신한다.

 

모든 동전에 대해 위와 같은 과정을 거친 후 구해진 잔돈의 개수 res 를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public 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));

        int n = 1000 - Integer.parseInt(br.readLine());
        int[] coins = {500, 100, 50, 10, 5, 1};

        int res = 0;
        for (int coin : coins) {
            if (n / coin != 0) {
                res += n / coin;
                n %= coin;
            }
        }

        bw.write(String.valueOf(res));
        bw.flush();
    }

}