알고리즘/백준

[BAEKJOON] 5585 거스름돈

응애~ 개발자 2022. 11. 23. 00:34
728x90
반응형

문제 요약

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

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

문제풀이

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

https://jih3508.tistory.com/70

 

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

이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 알고리즘은 이론상 설명 단순하고 다른 알고리즘에서 기초적으로

jih3508.tistory.com

  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);
	}
	
}
728x90
반응형