[PS] 그리디: 2720 세탁소 사장 동혁

문제 출처

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

문제 포인트

첫번째 입력은 몇번의 입력을 받을 지를 정한다.
거스름돈은 항상 5.00$ 이하이다.
입력받는 단위는 센트이다.

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

코드

import sys

fast_print = sys.stdout.write

bal_lines = int(sys.stdin.readline().rstrip())
bal_list = []

while bal_lines > 0:
    int_input = int(sys.stdin.readline().rstrip())
    if 0 <= int_input <= 500:
        bal_list.append(int_input)
        bal_lines -= 1

coins = [25, 10, 5, 1]

for bal in bal_list:
    while bal > 0:
        for coin in coins:
            temp_coin_cnt = bal // coin
            bal = bal % coin
            fast_print(str(temp_coin_cnt) + " ")
    fast_print("\n")

코멘트

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