[이것이 취업을 위한 코딩테스트다] ch.3 그리디 - 거스름돈

* 이 글은 이것이 취업을 위한 코딩테스트다 책을 기반으로 작성된 내용입니다.

 

그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 자주 출제됨.

 

[예제 3-1] 거스름돈

거스름돈으로 사용할 500원, 100원, 50원,10원짜리 동전이 무한히 존재한다고 가정

손님에게 거슬러 줘야할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수는? (N은 10의 배수)

 

[문제해설]

가장 큰 화폐 단위부터 돈을 거슬러 주면 거슬러 줘야 할 동전의 개수를 최소화 시킬수 있다.

즉, N을 500원으로 나누고 나머지를 100원으로 나누고... 이 과정을 10원까지 반복하면 된다.

 

[필요문법]

+= : 왼쪽의 피연산자에 오른쪽의 피연산자를 더한 후, 그 결과값을 왼쪽의 피연산자에 대입함.
%= : 왼쪽의 피연산자를 오른쪽의 피연산자로 나눈 후, 그 나머지를 왼쪽의 피연산자에 대입함.
% : 나머지 반환
// : 몫 반환

 

[코드]

n = 1260
count = 0

coin_types = [500,100,50,10]

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

print("거슬러 줘야 할 동전의 최소 개수 %d" %count)

 

 

처음 알고리즘을 접해서 이해하는데 시간이 꽤 오래걸렸다.

마지막 과정만 print하기 보단 한줄씩 이해하기 위해 

손으로 직접 계산해서 풀어보고, 아래 코드를 돌려 확인하면서 중간 과정을 이해해봤다.

n = 1260
count = 0

coin_types = [500,100,50,10]

for coin in coin_types:
  count += n//coin
  n %= coin
  
  print("coin = %d 일 때, count : %d, n : %d" % (coin, count,n) )
  
#결과 확인
coin = 500 일 때, count : 2, n : 260
coin = 100 일 때, count : 4, n : 60
coin = 50 일 때, count : 5, n : 10
coin = 10 일 때, count : 6, n : 0