[BOJ] 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)

출력

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

---

입력 예시

3
124
25
194

출력 예시

4 2 0 4
1 0 0 0
7 1 1 4

 

답안

코드

 

import sys

money = [25, 10, 5, 1]

N = int(sys.stdin.readline().strip())

for i in range(N):
    num = int(sys.stdin.readline())

    for j in range(len(money)):
        if num >= money[j]:
            print(num // money[j], end=' ')
            num %= money[j]
        else:
            print(0, end=' ')

풀이

이 문제는 주어진 거스름돈을 가장 효율적으로 동전으로 바꾸는 것입니다. 이를 위해 우리는 가장 큰 단위의 동전부터 차례로 거스름돈에 맞게 교환해 나가야 합니다. 주어진 동전의 종류는 쿼터($0.25), 다임($0.10), 니켈($0.05), 페니($0.01)로, 각각의 가치를 센트로 환산하면 25센트, 10센트, 5센트, 1센트입니다. 문제에서는 거스름돈 C가 센트 단위로 주어지므로, 이를 이용해 계산할 수 있습니다.

각 테스트 케이스마다 주어진 거스름돈에 대해 순서대로 쿼터, 다임, 니켈, 페니를 최대한 많이 사용하여 거슬러 줄 수 있는 개수를 계산합니다. 이때, 각 동전을 사용한 후에는 남은 거스름돈을 업데이트해야 합니다. 남은 거스름돈은 현재 거스름돈에서 현재 동전의 가치를 곱한 개수를 뺀 값이 됩니다. 이 과정을 모든 동전에 대해 반복하면, 각 동전의 최적 개수를 구할 수 있습니다.

코드를 살펴보면 아래와 같습니다. 

• money 배열은 각 동전의 센트 단위 가치를 저장합니다.
• 외부 루프(for i in range(N))는 각 테스트 케이스를 순회합니다.
• 내부 루프(for j in range(len(money)))는 각 동전의 종류를 순회하며, 현재 거스름돈에서 해당 동전으로 거슬러 줄 수 있는 최대 개수를 계산합니다. 이때, num // money[j]는 현재 동전으로 거슬러 줄 수 있는 최대 개수를 구하고, num %= money[j]는 사용한 후 남은 거스름돈을 업데이트합니다.
• 각 동전의 개수는 공백으로 구분하여 출력합니다. 만약 현재 동전으로 거슬러 줄 수 없는 경우(num < money[j]), 0을 출력합니다.