[Greedy] 거스름 돈

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

---

풀이

탐욕적인 아이디어: 가장 큰 화폐 단위부터 돈을 거슬러준다. 

---

코드

import Foundation

var n = Int(readLine()!)!
var result = 0
let coinTypes = [500, 100, 50, 10]

for coin in coinTypes {
    result += (n / coin)
    n %= coin
}

print(result)

---

분석

• 시간 복잡도 O(K)
  • 시간 복잡도는 동전의 총 종류에만 영향을 받는다.
  • 거슬러주어야하는 금액의 크기와는 무관하다.

---

그리디 알고리즘의 정당성

• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이다.
  • ex) 800원 → 500원 + 100*3이 최적
  • ex) 화폐단위에 400원이 있다면 400*2가 최적임
• 따라서 작은 동전들을 종합해 다른 해가 나올 수 없다.
• 따라서 첫 아이디어 가장 큰 화폐부터 돈을 거슬러주는 것이 항상 최적의 해이기 때문에 정당하다.

---

이것이 코딩테스트다를 읽고 정리한 글입니다.