거스름돈 최소 동전 개수

문제

거슬러 줄 금액 amount 와 사용 가능한 동전 단위 배열 coins 가 주어집니다. coins 는 "큰 단위 → 작은 단위" 순으로 정렬되어 있고, 항상 마지막 원소는 1 (1원)입니다. (즉, 큰 단위가 항상 작은 단위의 배수인 화폐 체계 — 그리디로 최적해를 얻을 수 있습니다.)

amount 를 만들 때 필요한 동전 개수의 "최솟값" 을 반환하세요.

예시

amount=1260, coins=[500,100,50,10,1]
  → 6   (500×2 + 100×2 + 50×1 + 10×1)
 
amount=80, coins=[500,100,50,10,1]
  → 4   (50×1 + 10×3)
 
amount=0, coins=[500,100,50,10,1]
  → 0
 
amount=4200, coins=[1000,500,100,50,10,1]
  → 6   (1000×4 + 100×2)

제약 조건

• 0 ≤ amount ≤ 1,000,000
• 1 ≤ coins.length ≤ 20
• coins 는 큰 단위부터 정렬, 마지막은 1

시간 복잡도 목표: O(coins.length)