[BOJ] 5585번 거스름돈

문제

www.acmicpc.net/problem/5585

5585번: 거스름돈

풀이

전형적인 그리디 알고리즘 문제이다. 거스름돈 종류 중 가장 큰 종류부터 순서대로 지불한다면, 최소의 갯수로 만들 수 있다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int[] changes = {500,100,50,10,5,1};
	static int change_num(int change) {
		int cnt =0;
		for(int i=0;i<6;i++) {
			cnt+=(change/changes[i]);
			change%=changes[i];
		}
		return cnt;
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	int change = 1000-Integer.parseInt(br.readLine());
    	
    	
    	//계산
    	System.out.println(change_num(change));
    	
	}
}