[구현/그리디] 백준 2720 세탁소 사장 동혁 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

2720번: 세탁소 사장 동혁

 

 

 

2. 문제 풀이

 25/10/5/1 단위인 거스름돈을 구하는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결​

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 동전 단위가 배수이므로, 최적성의 원리가 성립합니다. 따라서 그리디 알고리즘으로 쉽게 구할 수 있습니다.

 여기서 최적성의 원리는 '앞의 선택이 뒤의 선택에 영향을 미치지 않으며, 각 선택이 최적임을 보장'하는 것을 뜻하며, 단순히 큰 단위로 거슬러주는 게 가장 적은 거스름돈 갯수를 받게 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    change = int(input()) #거스름돈

    quarter = change//25
    change %= 25

    dime = change//10
    change %= 10

    nickel = change//5
    change %= 5

    penny = change
    print(quarter, dime, nickel, penny)

 가장 큰 동전 단위부터 거스름돈을 계산합니다.