728x90
최소 동전으로 거슬러 주기
최소 동전으로 돈을 거슬러 주는 함수를 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
728x90
'📊 Algorithm > Algorithm PS' 카테고리의 다른 글
[알고리즘 일기] 24. 지각 벌금 적게 내기 (0) | 2021.05.26 |
---|---|
[알고리즘 일기] 23. 최대 곱 구하기 (0) | 2021.05.23 |
[알고리즘 일기] 21. 최대 수익(Tabulation) (0) | 2021.05.22 |
[알고리즘 일기] 20. 최대 수익(Memoization) (0) | 2021.05.20 |
[알고리즘 일기] 19. 피보나치 수열(최적화) (0) | 2021.05.19 |