[알고리즘 일기] 22. 최소 동전으로 거슬러주기

 

문제 22. (2021-05-22)

 

최소 동전으로 거슬러 주기

최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현하시오.

 

 

주의사항

* 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다.

* 동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합니다.

 

 

❧ 테스트 셋

def min_coin_count(value, coin_list):
    #Code

#Test
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

 

❧ 출력 예시

10
5
49
70

 

---

❧ 정답

Try 1

def min_coin_count(value, coin_list):
    count = 0
    coin_list = sorted(coin_list, reverse=True)
    for i in range(0, len(coin_list)):
        if (value == 0):
            return count
        elif (value >= coin_list[i]):
            count += (value // coin_list[i])
            value -= ((value // coin_list[i]) * coin_list[i])
    return count

default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

 

 

---

Try 2

def min_coin_count(value, coin_list):
    count = 0
    coin_list = sorted(coin_list, reverse=True)
    for coin in coin_list:
        count += (value // coin)
        value %= coin
    return count

default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

1️⃣ Greedy 알고리즘 패러다임

2️⃣ 리스트의 내림차순 정렬 방법

reverse는 keyword-only argument 이기 때문에 keyword방식으로 인자를 전달해야 한다.

sorted(some_list, True) → sorted(some_list, reverse=True)

 

728x90