오늘의 문제
https://www.acmicpc.net/problem/11047
그리디 알고리즘을 검색하면 가장 먼저, 가장 많이 예시로 드는 문제 바로 동전 거스름돈 문제다.
포인트 쳌쳌
주어진 액수를 동전만으로 만들고자 한다면 액수가 가장 큰 동전을 먼저 사용할 때 가장 최적(최소)의 동전 개수 를 필요로 한다.
풀이순서는 굉장히 간단하다.
- 준규가 가진 동전의 종류를 리스트(또는 딕셔너리)로 구성한다.
- 내림차순으로 정렬하여 액수가 큰 순서대로 입력값을 나누며 동전 개수를 카운팅한다.
- 입력값이 0이 될 때까지 ‘나누기, 카운팅’ 작업을 반복한다.
이러한 개념 때문에 문제 해결 시 최적의 방법을 찾는다는 그리디의 개념을 설명할 때 쉬우면서도 가장 적합한 예시가 된 것이 아닌가 싶다.
풀이 코드
import sys
n, k = map(int, sys.stdin.readline().split())
coin = []
for i in range(n):
coin.append(input())
coin = list(map(int, coin))
coin.sort(reverse=True)
#print(coin)
idx = 0
cnt = 0
while idx < len(coin):
if k // coin[idx] > 0:
a = k // coin[idx]
k -= coin[idx]*a
cnt += a
else:
idx += 1
if k == 0:
break
print(cnt)
채점 결과
