백준(5585) - 거스름돈 Python

백준(5585) - 거스름돈

문제풀이 : 그리디 알고리즘, 파이썬

해결방법

거스름돈으로 최소의 갯수를 주기위해서는 큰 돈부터 차례대로 주면 되는 간단한 그리디 문제였다.

n = int(input())

money = 1000 - n
cnt = 0
changes = [500, 100, 50, 10, 5, 1]

def count(money, change, cnt):
    if money // change > 0:
        cnt += int(money // change)
        money = (money % change)
    return (money, cnt)

for change in changes:
    money, cnt = count(money, change, cnt)

print(cnt)