[Python] 백준 5585번 거스름돈(그리디)

문제

풀이

그리디 문제이다. 그리디의 특징은 매 순간마다 지금 최선의 값을 선택하는 방법이다. 

이 방법을 이 문제에 대입해 보면 어떠한 거스름돈이라도 가장 큰 수인 500원 부터 거슬러 주는 것이 가장 적은 숫자로 거슬러 주는 방법이 된다.

따라서 500원으로 나눈 몫, 100원으로 나눈 몫, 50원으로 나눈 몫... 이렇게 내려 가며 모두 거슬러 주면 된다.

n = int(input())

change = 1000-n

answer = 0

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

for i in yen:

    answer += change//i

    change %= i

print(answer)