백준 5585번: 거스름돈 [그리디][Greedy] - Java

www.acmicpc.net/problem/5585

5585번: 거스름돈

잔돈 중 가장 큰 것부터 거스름돈에 나눠본다.

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int[] coin = { 500, 100, 50, 10, 5, 1 };

		int price = 1000 - N;
		int ans = 0;

		for (int i = 0; i < coin.length; i++) {
			if (price >= coin[i]) {
				ans += price / coin[i];
				price -= coin[i] * (price / coin[i]);
				if (price == 0)
					break;
			}
		}
		System.out.println(ans);
	}

}