[BOJ / 백준] 5585번 거스름돈 python / 파이썬 그리디 알고리즘

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

5585번: 거스름돈

---

그리디 알고리즘으로 풀었다.

가장 큰돈부터 확인하는 그리디적인 접근을 하기 위해 동전의 값이 큰 것부터 리스트에 넣고 돌렸다.

# BOJ5585 거스름돈
N = int(input())
change = 1000 - N # 거스름 돈
ans = 0
# 500, 100, 50, 10, 5, 1 중 거스름 돈 갯수 가장 적게
coins = [500, 100, 50, 10, 5, 1]
for coin in coins:
    if coin <= change:
        ans += change // coin # 동전의 갯수
        change = change % coin # 남은 금액
        if change == 0: # 종료 조건
            break
print(ans)

모든 돈을 다 거슬러주고 남은 돈이 0원이면 for문을 끝까지 돌 지 않고 중간에 종료해줬다.