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

🥚문제

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

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

---

🥚입력/출력

• 입력
  첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
  둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
  
• 출력
  첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

🍳코드

# input
n, k = map(int, input().split())
coins = [x for x in range(n)]

# 내림차순으로 재정렬
for i in range(n):
    coins[n-1-i] = int(input())

ret = 0
for x in coins:
    # k == 0 : stop
    if k == 0:
        break

    # k원을 동전 x로 나눈 것의 몫이 0보다 클 때
    if k//x > 0:
        ret += k//x
        k %= x

print(ret)

---

🧂아이디어

전형적인 그리디 문제!

위 문제를 그리디 알고리즘으로 해결할 수 있는 이유는

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를 들어 800원을 만드는 데 화폐 단위가 500원, 400원, 100원인 경우 그리디 알고리즘으로는 4개의 동전(500 + 100 + 100 + 100)이라고 나오지만 사실 최적의 해는 2개의 동전(400원 + 400원)이다.

다시 말해 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로 '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하는 작업을 수행하면 된다' 는 아이디어가 정당하다.

(출처: 이것이 코딩테스트다 with 파이썬, 90-91p.)