[알고리즘] 백준 5585번 거스름돈 파이썬

문제

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

5585번: 거스름돈

 

문제 접근

큰 돈부터 거슬러 준다. 그리디다.

 

코드

n = int(input())

coins = [500,100,50,10,5,1]
r = 1000-n
count =0
for coin in coins:
    if r//coin > 0:
        count += r//coin
        r = r%coin

print(count)

 

배운점

이제 암기해라. 이런 느낌의 그리디 문제는 배열과 정렬이다!