[그리디 알고리즘] 예시 문제 - 거스름 돈

거스름 돈

1) 해결 아이디어

최적의 해: 가장 큰 화폐 단위부터 돈을 거슬러 주기 (500->100->50->10)

2) 정당성 분석

Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는?

동전의 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 최적의 해가 나올 수 없기 때문

if) 화폐 단위 500, 400, 100원으로 800원을 거슬러 줘야 한다면?

그리디 해: 500 * 1 + 100 * 3 => 4개

최적의 해: 400 * 2 => 2개

 

3) 소스코드

n = 1260
count = 0  # 동전 개수

# 큰 단위부터 확인
coinList = [500, 100, 50, 10]

for coin in coinList:
  count += n // coin  # 해당 동전 단위로 거슬러 줄 수 있는 동전 개수
  n %= coin      # 잔액
  
print(count)

4) 시간 복잡도 분석

화폐의 종류=K일 때, 소스 코드의 시간 복잡도=O(K)

이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과 무관하며 동전 단위의 개수에만 영향을 받음