[파이썬] 백준 5585 : 거스름돈

[파이썬] 백준 5585 : 거스름돈

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

5585번: 거스름돈

브론즈 2

그리디 알고리즘

---

접근

 

그리디 알고리즘의 가장 기본적인 문제이다.

거슬러야하는 돈을 단위가 큰 순서대로 리스트에 담고, 몫과 나머지를 적절히 활용하면 쉽게 구할 수 있다.

그리디 알고리즘은 최적의 해를 빠르게 구하기 위해 현재 상황에서 당장 좋은 것만 고르는 방법이다.

 

코드 풀이

import sys
coins = [500, 100, 50, 10, 5, 1]
give = int(sys.stdin.readline())
changes = 1000 - give
cnt = 0
for c in coins:
    cnt += changes // c
    changes %= c
print(cnt)

 

1000원에서 입력한 값을 빼준값이 거슬러줘야하는 값이다.(changes)

coins리스트에 거슬러주는 돈의 단위가 큰 순서대로 정리한다.

반복문을 사용해 차레대로 거슬러줘야하는 값에 대한 몫과 나머지를 구한다.

몫은 잔돈의 개수, 나머지는 거슬러주고 남는 값이 된다.