[백준 5585] 거스름돈 - 자바

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

1. 풀이

---

그리디 알고리즘을 사용하면 쉽게 풀 수 있는 문제입니다.

 

동전의 큰 숫자부터 나누어가며 나눠지면 나눠지는 만큼 누적하면 됩니다.

 

2. 코드

---

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = 1000 - sc.nextInt();
		
		int[] coins = {500,100,50,10,5,1};
		
		int result = 0;
		for(int i = 0; i < coins.length; i++) {
			if(n / coins[i] != 0) {
				result += n / coins[i];
				n %= coins[i];
			}
		}
		
		System.out.println(result);
		
		sc.close();
		return;
	}
}