자료 구조 문제만 풀다가 그리디 유형의 문제도 병행하기로 했습니다. 그리디 알고리즘에 대한 개념글을 보고 오시면 도움이 될 것입니다.
오늘 문제는 그리디 알고리즘을 아신다면 가장 많이 보시는 거스름돈을 줄 때 최소의 동전으로 주는 문제입니다.
1. 오늘의 학습 키워드
- 그리디 알고리즘
2. 문제: 세탁소 사장 동혁 (2720번)
- 단계: 🥉 브론즈 3티어
- 알고리즘 분류: 수학, 그리디 알고리즘, 사칙연산
- 출처: https://www.acmicpc.net/problem/2720
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 41985 | 29020 | 25962 | 69.886% |
문제
미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.
동혁이는 리암에게 실망했다.
리암은 거스름돈을 주는 것을 자꾸 실수한다.
심지어 $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)
출력
각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.
예제 입력 1 복사
3
124
25
194예제 출력 1 복사
4 2 0 4
1 0 0 0
7 1 1 4출처
ICPC > Regionals > North America > Greater New York Region > 2006 Greater New York Programming Contest A번
- 문제를 번역한 사람: baekjoon
알고리즘 분류
3. 나의 풀이
문제 접근 방법
그리디 알고리즘은 문제를 해결할 때 매 순간 가장 최적의 선택을 하는 방법입니다. 즉, 매 단계에서 가능한 가장 큰 동전부터 사용해 나가면 최종적으로 최적의 해답에 도달할 수 있습니다.
이 문제에서 우리는 가장 큰 단위의 동전부터 차례대로 거슬러 주면 됩니다. 예를 들어, 124센트를 거슬러 준다고 할 때, 가장 큰 단위인 25센트(쿼터)를 최대한 많이 사용한 후, 남은 금액에 대해 같은 방식으로 처리하면 됩니다.
문제 풀이 단계
- 쿼터(25센트)를 먼저 계산하여 최대한 많이 사용합니다.
- 남은 금액에서 다임(10센트)을 최대한 많이 사용합니다.
- 그 다음 니켈(5센트)을 계산하고, 마지막으로 페니(1센트)로 남은 금액을 처리합니다.
동전 문제에서 그리디 알고리즘이 최적해를 보장하는 이유
그리디 알고리즘이 작동하는 중요한 이유는, 미국의 동전 체계가 잘 설계되어 있기 때문입니다. 각 동전 단위가 배수 관계가 아니더라도, 큰 단위의 동전을 먼저 사용하는 것이 항상 최적의 해답을 보장합니다.
예를 들어, 30센트를 거슬러 줄 때, 25센트(쿼터) 한 개와 5센트(니켈) 한 개를 주는 것이 10센트 세 개로 거슬러 주는 것보다 더 적은 동전을 사용합니다. 즉, 큰 동전을 먼저 사용하는 방식이 항상 적은 동전으로 동일한 금액을 만들 수 있는 이유는 동전의 단위가 적절히 설계되었기 때문입니다.
배수 관계와 그리디 알고리즘
일반적으로 그리디 알고리즘은 동전 단위가 배수 관계일 때 더 직관적으로 적용됩니다. 예를 들어, 25센트는 5센트와 1센트의 배수이기 때문에, 큰 동전을 먼저 사용한 후 나머지를 작은 동전으로 거슬러 주는 것이 항상 최적의 방법이 됩니다.
하지만 미국 동전 체계에서는 배수 관계가 아니더라도 그리디 알고리즘이 최적해를 보장합니다. 이는 각 동전 단위가 더 적은 동전으로 금액을 구성할 방법이 없도록 설계되어 있기 때문입니다.
알고리즘 설명
- 큰 단위부터 처리: 먼저 가장 큰 단위인 쿼터로 거슬러 줄 수 있는 최대 개수를 구하고, 남은 금액을 다임, 니켈, 페니로 처리합니다.
- 나머지 계산: 매번 동전을 사용한 후 남은 금액은 해당 동전의 단위로 나눈 나머지로 계산합니다.
코드 구현
이제, 이 문제를 해결하기 위한 파이썬 코드를 살펴보겠습니다.
import sys
# 테스트 케이스의 수 입력
T = int(sys.stdin.readline().strip())
# 각 테스트 케이스에 대해 처리
for _ in range(T):
# 거스름돈 입력 (센트 단위)
charge = int(sys.stdin.readline().strip())
# 동전의 단위에 맞춰 개수 계산
for i in [25, 10, 5, 1]:
print(charge // i, end=' ') # 동전의 개수를 출력
charge %= i # 나머지 금액 갱신
print() # 다음 테스트 케이스 출력을 위해 줄바꿈마무리
동전 거스름돈 문제는 그리디 알고리즘을 통해 쉽게 해결할 수 있는 대표적인 문제입니다. 미국의 동전 체계가 이 문제를 최적의 방법으로 해결할 수 있도록 설계되어 있기 때문에, 큰 단위 동전부터 사용해도 항상 최적의 해답을 얻을 수 있습니다. 이번 글에서는 그리디 알고리즘의 적용과 그 정당성을 설명하고, 파이썬 코드 구현을 통해 문제를 해결하는 방법을 함께 살펴보았습니다.
이 문제는 알고리즘 학습에서 그리디 전략을 이해하고 연습하는 데 매우 적합한 문제입니다. 동전 문제 외에도 다양한 최적화 문제에서 그리디 알고리즘이 어떻게 적용될 수 있는지 고민해보세요!
그리디 알고리즘을 공부하고 본격적으로 푼 첫문제입니다. 무조건 전 성공할 것입니다!!
부족한 내용이나 질문이 있으시다면 댓글로 남겨주세요 :)
읽어주셔서 감사합니다.
