백준 5585 거스름돈 (python)

그리디알고리즘 공부중

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘.

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게모르게 제시해준다.

거스름돈문제는 그리디알고리즘을 대표하는 문제

 

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

5585번: 거스름돈

 

coin = [500, 100, 50, 10, 5, 1]

price = input()
left = 1000 - int(price)

count = 0

for c in coin:
    count += left//c
    #print('count: ', count, 'left: ', left)
    left = left % c

print(count)