백준 5585: 거스름돈 (Python)

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

5585번: 거스름돈

 

n = int(input())

cash = [500, 100, 50, 10, 5, 1]
k = 1000 - n
cnt = 0

for i in cash:
    cnt += k // i
    k %= i

print(cnt)

 

 

그리디 알고리즘을 거스름돈 문제를 예시로 들어서 공부했기 때문에 쉽게 풀 수 있었다!