1) 최소 동전으로 거슬러주기(greedy algorithm)

Greedy Algorithm

가장 좋아보이는 것을 답으로 선택한다.

따라서 정확한 답이 아닐 수 있다.

두 가지 조건을 충족하면 최적의 답을 도출할 수 있다.

만약 문제가 최적 부분 구조를 가졌고, 탐욕적 선택 속성을 가졌다면 

Greedy Algorithm을 활용해도 최적의 답을 얻어낼 수 있다.

 

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0
    # coin_list의 값들을 큰 순서대로 본다
    for coin in sorted(coin_list, reverse=True):
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
        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))

#결과 : 
10
5
49
70