[그리디] 11047번 : 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

링크 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

해결 방법

해당 문제는 탐욕법인 그리디를 사용하여 해결 할 수 있는 문제다.

 

주어진 가장 작은 값에서 시작하여 큰 값으로 나누는 방법으로 정답을 유추해 낼 수도 있지만 그렇게 되면 매우 많은 경우의 수가 존재하므로 큰 값에서 작은 값으로 범위를 좁혀가며 진행하는 것이 더 경우의 수를 줄일 수 있을 것 같아 입력 값을 reversed 함수를 사용하여 진행했다.

 

import sys

N,K = map(int,sys.stdin.readline().split())

coins = [int(sys.stdin.readline()) for _ in range(N)]
cnt = 0
for coin in reversed(coins): # 큰 값부터 비교
    if K//coin != 0: # coin이 K보다 작은 경우(몫이 존재)
        cnt+=K//coin # 나누어 떨어지는 동전의 수 더하기
        K = K%coin # 나누어 떨어지지 않는 동전 초기화
print(cnt)

 

for 문을 통해 큰 값부터 진행되는데 만약 입력으로 주어진 K보다 크다면 경우의 수가 존재할 수 없으므로 계산 없이 넘어가게 된다.

 

만약 K보다 작다면 경우의 수가 존재 할 수 있는데 이때, 나누어 떨어지는 개수를 더해가면 가장 적은 지폐를 사용하는 출력값을 구할 수 있다.