[백준/BOJ] 2720번: 세탁소 사장 동혁 (Python) 풀이

Beakjoon Online Judge(BOJ) 의 2720번 문제인 '세탁소 사장 동혁' 을 풀어보았다.

[문제 정보]

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

 

---

문제 개요:

[ 문제 ]

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.

동혁이는 리암에게 실망했다.
리암은 거스름돈을 주는 것을 자꾸 실수한다.
심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다!

어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오.

거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

[ 입력 ]

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다.
C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

[ 출력 ]

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

이 문제의 요점은 거스름돈을 거슬러 주어야 하는데, 동전의 개수를 최소화해야 한다는 것.

즉, 그리디(탐욕) 알고리즘을 사용해야 한다.

 

그리디 알고리즘(greedy algorithm) 이란?

최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에(매 단계마다) 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (출처: 위키피디아)

 

하지만, 매 단계마다에서는 최적의 선택을 하여도, 마지막에 종합적으로 봤을 때 결과가 최적이라는 보장은 없다.

 

이 문제에서는 동전의 개수를 최소화해야 하므로, 금액이 높은 동전부터 거슬러주어서 총 거스름돈 액수를 빠르게 감소시켜야 할 것이다. 그러므로 매 순간마다 최선의 선택(금액이 높은 동전부터 거슬러 주기)을 해야 하는 그리디 알고리즘을 사용해야 하는 것이다.

위 예제에서 볼 수 있듯이 테스트 케이스 수만큼 거스름돈을 센트 단위로 입력받고, 각 필요한 쿼터, 다임, 니켈, 페니의 개수를 순서대로 출력해주면 된다.

알고리즘:

1. 테스트 케이스 수 T를 먼저 입력받고, 각 거스름 동전의 가격 정보가 담긴  money 리스트를 만든다.
   
   
2. T번 반복하는 반복문을 만든다. (거스름돈의 액수를 T번 입력받는 역할)
3. 거스름돈의 액수 C를 입력받는다.
   
   
4. 입력받은 C를 바탕으로 거스름돈 동전 개수(4개) 만큼 반복하는 반복문을 만든다. (입력받은 C의 필요한 최소 동전 개수를 구한 뒤 출력하는 역할)
5. 입력받은 C에서 금액이 높은 동전 순으로 동전 액수로 나눈 몫을 출력하고, 동전 액수만큼 뺀 나머지 금액은 C에 저장하여 모두 거슬러주어 남은 돈이 0원이 될때까지 계산을 반복한다.
   
   
   

코드:

T = int(input())
money = [25, 10, 5, 1]

for i in range(T):
    C = int(input())

    for j in range(len(money)):
        print(C // money[j], end=' ')
        C = C % money[j]
        
    print()

위 풀이에 대한 질문이나, 틀린 정보가 있다면 댓글로 말씀해 주시면 감사하겠습니다!