카운터에서 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전들이 무제한으로 있을 때
거스름돈 N원을 동전의 갯수를 최소한으로 사용하여 가글러 준다.
(단, 거스름돈 N은 10의 배수)
제일 큰 단위인 500원으로 거슬러 줄 수 있을 만큼 거슬러 준 뒤, 100원, 50원, 10원 순서로 거슬러 준다.
예시: 2,670원을 거슬러 준다고 하면
import Foundation
func coinCountMin(_ change: Int) {
var money = change
let coin_list = [500, 100, 50, 10]
var coinCount = 0
for coin in coin_list{
let count = money / coin
if count != 0 {
coinCount += count
money -= coin * count
} else { continue }
}
print(coinCount)
}
coinCountMin(1260)
for coin in coin_list
구문에서 알 수 있듯이, 화폐의 종류만큼 반복 수행이 필요하다.실제 최적해가 그리디 알고리즘의 해에서 절반으로 줄어든 것을 알 수 있다.
맨 처음 예제에서 500원, 100원, 50원, 10원
이듯이 각 단위들이 서로 배수 형태로 이뤄져야 한다.