[BAEKJOON] 5585 거스름돈

문제 요약

• 알고리즘 분류: 그리디
• 난이도: Bronze2
• 문제내용:
  • 잔돈은 500, 100, 50, 5, 1 있다.
  • 내가 가진돈은 1000엔 지폐 한 장을 내면 거스름돈 받아야 최소 개수를 구해라.
• 사이트: https://www.acmicpc.net/problem/5585

5585번: 거스름돈

문제풀이

 이번 문제는 그리디 알고리즘 중 그리디 알고리즘이다. 그리디 알고리즘의 관련 내용은 아래 사이트에 확인 해보면 되고 예제중에 거스름돈이 있으니 그것 확인 해보면 문제를 풀수 있다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

1.  1000을 뺀 나머지 돈을 구한다.
2. 500, 100, 50, 10, 5, 1 순으로 잔돈을 나누어서 개수에 추가한다.
3. 잔돈에서 지금 나눈수의 나머지를 잔돈에 저장한다.

Code

Python

change = 1000 - int(input())
count = 0
moneys = [500, 100, 50, 10, 5, 1]
for money in moneys:
    count += change // money
    change %= money

print(count)

Java

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int change = 1000 - Integer.parseInt(br.readLine());
		int[] moneys = {500, 100, 50, 10, 5, 1};
		int count = 0;
		for(int money : moneys) {
			count += change / money;
			change %= money;
		}
		System.out.println(count);
	}
	
}