← 9주차 · 그리디
쉬움그리디

거스름돈 최소 동전 (배수 화폐)

거슬러 줄 금액 amount와 동전 단위 배열 coins가 주어져요. amount를 만드는 데 필요한 동전의 최소 개수를 반환해요. 각 단위는 무한히 쓸 수 있어요.

이 문제의 coins는 큰 단위가 항상 작은 단위의 배수가 되도록 주어져요(예: 1, 5, 10, 50, 100). 이 조건에서는 큰 단위부터 최대한 쓰는 그리디가 항상 최적이에요 — 큰 단위를 덜 쓰고 작은 단위로 메우면 개수가 늘기만 하거든요.

amount는 주어진 동전들로 항상 만들 수 있어요(1원이 포함돼요).

예시

예시 1
입력
amount = 1260, coins = [1, 5, 10, 50, 100, 500]
출력
6
설명
500×2 + 100×2 + 50×1 + 10×1 = 1260, 동전 6개.
예시 2
입력
amount = 4, coins = [1, 5, 10]
출력
4
설명
5로는 넘치니까 1원 4개를 써요.

제한 사항

  • 0 ≤ amount ≤ 1,000,000,000
  • 1 ≤ coins.length ≤ 20, coins에는 1이 포함돼요.
  • coins를 내림차순으로 보면 각 단위는 바로 다음 단위의 배수예요.
동전을 내림차순으로 정렬하고, 각 단위마다 Math.floor(amount / coin)개를 쓰고 amount %= coin으로 남은 금액을 줄여요.
javascript
function minCoinsGreedy(amount, coins) {
  const sorted = [...coins].sort((a, b) => b - a);
  let count = 0;
  for (const coin of sorted) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
이전 문제중복 없는 가장 긴 부분 문자열
다음 문제회의실 배정
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.