[알고리즘] 그리디 알고리즘 실전문제1: 거스름돈 문제

문제상황

거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정.
거스름돈이 N원일 때 거슬러줘야 하는 동전의 최소 개수를 구하라.

변수 설정

변수	설명
N	거스름돈
count	거슬러줘야 하는 동전의 최소 개수
k	동전의 종류 수

 

풀이 전략

거슬러줘야 하는 동전을 최소화하기 위해서는 크기가 큰 500원을 최대로, 그 다음에는 100원을 최대로 ... 사용해야 한다.

일단 N을 500으로 나누었을 때, 몫은 '필요한 500원 동전의 개수'에 해당한다.
그 나머지를 100으로 나누었을 때, 몫은 '필요한 100원 동전의 개수'에 해당한다.
...
이 과정을 10원짜리 동전까지 진행하는 코드는 다음과 같다.

N = 1260
count = 0

list = [500, 100, 50, 10]

for coin in list:
	N = N % coin
    count += N // coin
    
print(count)

동전의 종류가 K개라고 할 때, 이 소스코드의 시간복잡도는 O(K)이다. *시간 복잡도, 큰 수의 법칙
즉, 이 알고리즘의 시간 복잡도는 K에만 영향을 받는다.

참고로, 이 문제를 그리디 알고리즘으로 해결할 수 있는 이유는
동전 중 큰 단위가 작은 단위의 배수이기 때문이다.
아닌 경우, 그리디 알고리즘을 적용할 수 없음을 기억하자!

 

참고: 이것이 코딩테스트다