5585. 거스름돈

동전 문제는 그리디 알고리즘이 되는 이유가

예를 들어 화폐가 500원, 100원 두 가지라면 500과 100의 최소공배수가 더 작은 수(100)이기 때문이라고 한다.

100x5=500으로 표현 가능하지만 이러할 경우 500으로 표현하는 것이 유리하기 때문에,

내림차순으로 정렬한 후에 그리디 알고리즘으로 해결 가능하다는 것 같다.

만약 화폐가 500원, 400원이라면 500은 400의 자연수 배수로 표현할 수 없기 때문에 그리디 알고리즘으로 풀 수 없다고 한다.

 

answer = 0

price = int(input())
change = 1000 - price
bank = [500, 100, 50, 10, 5, 1]

for coin in bank:
    if change >= coin:
        answer += change // coin
        change %= coin
        if change == 0:
            break

print(answer)