[백준 5585번] 거스름돈

n = int(input())

change = 1000 - n

money_unit = [500,100,50,10,5,1]

count = 0

for i in money_unit:
  if change//i > 0:
    count += (change//i)
    change %= i

print(count)

이번 문제는 그리디 알고리즘의 대표적인 기본 문제로, 그리디 알고리즘을 처음 공부할 때 내용을 이해하기 좋은 문제이다.

 

이 문제의 핵심은 잔돈을 최대한 적은 개수의 잔돈으로 거슬러주는 것인데, 위 문제와 같은 경우에는 모든 돈의 단위가 서로 배수 관계를 가지고 있기 때문에 단순히 금액이 큰 순서대로 거슬러 주어도 문제없이 풀 수 있다.

 

만약에 잔돈이 800원이고 가진 돈의 단위가 [500, 400, 100] 이라면 단순히 Greedy로 풀이하면 정답이 나오지 않는 다는 것을 알 수 있다.

 

이처럼 그리디 알고리즘 문제는 문제의 조건이 그리디를 사용하기에 적합한지 먼저 고려해보아야 한다 :)