[그리디] 거스름돈 문제

예제 3-1. 거스름돈 문제 

 

- 거스름돈은 500원, 100원, 50원, 10원 동전이 무제한 존재한다.

- 손님에게 거슬러줄 돈은 N원이다.

- 거슬러 줘야할 동전의 최소 개수는 ?

 

import time
start_time = time.time()
##

n = 1260
count = 0
coin_types = [500, 100, 50, 10]

for coin in coin_types:
  count  = count + ( n // coin )  # count
  n      = n % coin

print(count)

##
end_time = time.time()
print ("TIME : ", end_time - start_time)

 

- 거슬러 주어야할 돈은 1260원이다.

- 500원으로 나누게되면 ( 1260 / coin_types[0] = 2 ) 거슬러줄 동전의 갯수가 된다.

- 2개의 동전 (1000원) 을 거슬러주었으며, 이를 count 에 합해준다.

- 다음 연산을 진행할 n은 거슬러준 돈만큼을 제외시켜야한다. 이건 위에서 나눠주고 남은 나머지가된다 ( 1260 % coin_types[0] = 260 )

- 같은 연산을 계속해서 진행해준다.

- 시간복잡도는 ,배열의 갯수(K) 만큼 연산을 진행해주어야하므로 O(K) 가 된다.