[03그리디] 3-1 거스름돈(p87~p90)

[예제3-1 거스름돈]

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

[코어 아이디어]

- 가장 큰 화폐 단위부터 돈을 거슬러주는것.

   step 0 초기단계 - 잔액 1260원

   step 1 500원 2개 - 잔액 260원

   step 2 100원 2개 - 잔액 60원

   step 3 50원 1개 - 잔액 10원

   step 4 10원 1개 - 잔액 0원

 

   -> 총 손님이 받는 최소 동전의 개수는 6개

 

[파이썬 코드 구현]

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

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

 

 - 시간복잡도: O(K) - 단일 for문으로, 화폐의 종류만큼 반복을 수행하기 때문

 

[for문 상세분석]

1. for coin in coin_types:

   - coin_types 안에 있는 원소 수 만큼 for문이 진행되며, coin에는 리스트의 순서대로 담긴다.

   - 즉 0번째 for문에는 500이 담긴다.

 

2. count += (n // coin)

   - n은 잔액을 의미한다. (n // coin)의 경우 잔액에서 coin을 나눈 몫에 해당한다.

   - 즉, 0번째 for문으로 생각해보면 coin이 500이므로, (1260 // 500)의 경우 2가 나온다.

   - 이후 +=는 count = count + (n // coin)과 동일하므로, count가 2가 된다.

 

3. n %= coin

   - n이 잔액이고, % 연산자는 나머지 연산자이다. 즉, (1260 % 500)의 경우 260이 되는데, %= 이므로 n은 260이 된다.

 

 

여기까지가 책에서 제공하는 답안이지만, 실제 코드를 돌려보면 count의 수만 딱 출력한다.
실제로 n이 깎여나가는 과정을 보고싶지 않은가?

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    #------------------------#
    print("잔액은 ", n,"입니다.")
    #------------------------#
    count += (n // coin)
    n %= coin
    
    
print(count)

 

 - 잔액이 1260부터 시작해 큰 동전 순서대로 잘 거슬러주는것을 확인할 수 있다.