그리디(탐욕법) 알고리즘 - 거스름돈 문제

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 보르는 방법, 닫순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 꼭 필요!

 

 

거스름돈 문제

카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, N은 10의 배수

 

해결 방법

- 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다.

    >> N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러주고 이후 단위도 똑같이 반복

 

- 최적의 해가 보장되는 이유 : 큰 단위가 항상 작은 단위의 배수이기 때문! 

    >> 800원을 거슬러 주어야 하는데 단위가 500,400,100 이라면 400원 두개 주는게 최적의 해가 된다.

 

답안 예시

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
	count += n//coin
    n%=coin

print(coin)

 

화폐의 개수가 K라고 했을때, 시간 복잡도는 O(K)