[Python | 11047] 동전 0

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

---

문제 설명

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

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

 

📌 시간 제한: 1초

---

입력

첫째 줄에 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

문제 접근

우리는 N개의 동전 종류를 가지고 있고, 각각의 동전 가치는 오름차순으로 주어진다. 목표는 K원을 만들기 위해 필요한 동전 개수의 최솟값을 구하는 것인데, 여기서 핵심은 동전 개수를 최소로 해야 한다는 점이다.
그래서 가장 큰 동전부터 하나씩 K원에 맞춰 써보는 방식으로 접근했다.

 

🤔 이게 왜 그리디 알고리즘이지?

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 전략이다. 이 문제에서는 "현재 만들 수 있는 가장 큰 동전부터 최대한 많이 사용하는 것"이 가장 좋아 보이는 선택일 것이다. 그렇지만 아무 때나 그리디가 맞는 건 아닌데, 이 문제에서는 다행히도 동전들이 서로 배수 관계에 있어서, 큰 동전부터 최대한 쓰는 것이 항상 최적의 선택이 된다!

 

💡 배수 관계란?

동전들 사이가 정수 배수 관계를 이룬다는 뜻이다.
예를 들어 1, 5, 10, 50, 100, 500 이런 식으로 구성돼 있다면,

• 5는 1의 배수
• 10은 5의 배수
• 50은 10의 배수 …

이렇게 구성돼 있을 때는 큰 동전부터 쓰는 방식이 항상 최적.

---

구현

1. 동전을 큰 값부터 내림차순으로 정렬하고,
2. 각 동전으로 최대로 몇 개 쓸 수 있는지 계산
3. 그만큼 금액에서 빼주고,
4. 남은 금액에 대해 더 작은 동전으로 반복

이 과정을 반복하면 항상 최소 개수의 동전으로 금액을 만들 수 있다.

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

coins.sort(reverse=True)

cnt = 0
for coin in coins:
    if k >= coin:
        cnt += k // coin
        k %= coin

print(cnt)