5585. 거스름돈

(브론즈 II) 탐욕 알고리즘을 이용한 거스름돈 구하기!

1. 풀이

현재 상황에서 가장 최선인 것을 선택하면 되는 그리디 문제이다.

가장 큰 액수의 동전부터 차례로 거슬러 줄 경우에 거슬러 줄 동전의 개수가 가장 적어진다.

2. 코드

coin_types = [500, 100, 50, 10, 5, 1]

money = 1000 - int(input())
count = 0

for coin in coin_types:
    count += money // coin
    money %= coin

print(count)