[그리디] 거스름돈 (파이썬)

당신은 음식점의 계산을 도와주는 점원이다.

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

---

N = int(input())
cnt = 0

coin = [500, 100, 50, 10]

while N >= coin[0]:
  N = N - coin[0]
  cnt += 1
  print(N, cnt)
while N < coin[0] and N >= coin[1]:
  N = N - coin[1]
  cnt += 1
  print(N, cnt)
while N < coin[1] and N >= coin[2]:
  N = N - coin[2]
  cnt += 1
  print(N, cnt)
while N < coin[2] and N >= coin[3]:
  N = N - coin[3]
  cnt += 1
  print(N, cnt)

print(N, cnt)

최소한의 개수의 동전을 거슬러줘야 하기 때문에, 가장 큰 화폐 단위로 최대한 많이 주면 문제를 해결할 수 있다.

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위의 동전을 조합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 위 문제를 해결할 수 있다.