백준) 거스름돈-python

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

5585번: 거스름돈

a = int(input())
a = 1000 - a
answer = 0

while a > 0:
  if a >= 500:
    answer += a // 500
    a = a % 500

  elif a >= 100:
    answer += a // 100
    a = a % 100

  elif a >= 50:
    answer += a // 50
    a = a % 50

  elif a >= 10:
    answer += a // 10
    a = a % 10

  elif a >= 5:
    answer += a // 5
    a = a % 5

  elif a >= 1:
    answer += a // 1
    a = a % 1

print(answer)

 

사실 그리디의 기본 중 기본인 문제였다.

설명할 것은 딱히 없지만 하나 중요한 점은,

해당 풀이가 성립하기 위해선 거스름돈이 각각의 거스름돈으로 나뉘어야 성립이 가능하다.

 

즉, 큰 수가 다른 작은 수들로 나누어 떨어질 경우에만 성립이 가능한 풀이이다.