문제풀기 : 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현

문제 5.

• 지불해야 하는 값이 4720원일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 방법
• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현

coin_list=[1, 100, 50, 500]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

min_coin_count(4720, coin_list)

(31, [[500, 9], [100, 2], [50, 0], [1, 20]])

 

1. def min_coin_count(value, coin_list):         함수 선언

 

2. total_coin_count = 0                                    어느 동전을 몇개 썻는지 출력하는 리스트 

 

3. coin_list.sort(reverse=True)                       reverse로 큰 순서대로 내림차순 정렬

 

4. for coin in coin_list:                                      큰 동전부터 차례대로 계산

 

 

5. coin_num = value // coin                             큰 값의 동전으로 해당 비교 금액을 채워야 하기 때문에, 몫을 구해서 동전의 개수를 구                                                                               한다 - 지불값을 동전으로 나눈 몫을 coin_num에 대입

 

6. total_coin_count += coin_num                   coin_num을 전체 동전수에 추가, 전체 코인 개수를 해당 동전 개수 만큼 올리자

 

7. value -= coin_num * coin                            지불 값에 동전 사용한 만큼 빼주기

 

8. details.append([coin, coin_num])               코인금액과 갯수를 기록

 

9. return total_coin_count, details

 

 

4890원을 지불할 때

1. 4870 // 500   9개의 500원 동전으로 4500원(해당 금액을 넘지 않으면서 500원으로 지불할 수 있는 최대 금액)을

지불한다.)

2. (4870-4500) // 100   3개의 동전으로 300원을 지불.

3. (370-300) // 50   1개의 동전으로 50원을 지불.

4. (70-50) // 10 2개의 동전으로 20원을 지불.

 

 

4870원이라는 금액을 지불하기 위해 사용해야 하는 최소 동전 수는 15개