[백준 5585문제] 그리디 알고리즘 - 거스름돈 ( python3)

 

가장 적게 잔돈을 줘야하니까, 거스름돈중에 큰 수 부터 나눠주고 남은돈을 다시 카운트 하면된다. 

380엔을 냈고, 620엔의 거스름돈을 받아야하는데 이때 거스름돈 단위중에 가장 큰 단위부터 사용하면된다.

500엔으로 나눈 수를 count 해주고, 나머지값을 잔돈으로 넣어주고 다시 그다음으로 큰 100엔으로 나눠주다보면 500엔 100엔 10엔을 2번 사용해서 총 4번으로 값을 출력할수있다 

n =int(input())

change = 1000- n
coins = [500,100,50,10,5,1]
count = 0

for coin in coins:
    count += change // coin
    change %=coin

print(count)