문제 출처

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

포인트

• 그리디 문제는 현재 상황에서 가장 좋은 선택만을 반복해서 결과에 도달하는 방식을 사용한다.
  대부분의 경우 최적해를 찾을 수 없지만, 최적해를 찾는 걸 보장할 수 있는 경우 가장 좋은 방식이다.

• 파이썬으로 코딩테스트를 풀 때 입출력을 빠르게 하기 위해 sys 라이브러리 사용

import sys

print = sys.stdout.write

price = int(sys.stdin.readline().rstrip())

bal_list = [500, 100, 50, 10, 5, 1]
coin_cnt = 0

bal = 1000 - price

while bal > 0:
    for _ in bal_list:
        coin_cnt += bal // _
        bal = bal % _

print(str(coin_cnt))

코멘트

잔돈을 거슬러 주는 경우가 가장 대표적으로 그리디 알고리즘을 사용했을 때 최적해를 보장하는 상황이다.