백준 알고리즘 5585번 거스름돈(python)

11047번 동전 0과 거의 똑같은 문제이다.

거스름돈보다 싼 동전 중에서 제일 큰 것부터 순서대로 꽉꽉 채운다는 느낌으로 풀면 된다.

change = 1000 - int(input())
cnt = 0
for c in [500, 100, 50, 10, 5, 1]:
    if c <= change:
        cnt += change//c
        change %= c
    if change == 0:
        break
print(cnt)