백준 5585 거스름돈

그리디 알고리즘 연구

Greedy Algorithm은 기준에 따라 좋은 것을 선택하는 알고리즘입니다.

문제에서 “큰 것부터”, “작은 것부터” 등의 기준을 제시한다.

변경 문제는 그리디 알고리즘을 나타내는 문제입니다.

https://www.acmicpc.net/problem/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)