[코드잇] 그리드 알고리즘 최소동전 건네주기

최소동전 건네주기.py

탐욕적 선택법을 사용하려면

최적 부분 문제
     부분 문제들의 최적의 답을 이용해서
       기존문제의 최적의 답을 구할 수 있다는 것
과

탐욕적 선택 속성
    각 단계에서의 탐욕스런 선택이
      최종 답을 구하기 위한 최적의 선택

두가지가 만족해야만 정확한 답을 구할 수 있다.


//100 70 10 인 문제는 탐욕적 선택이 되지않음
ex) 140원 을 걸러줄때 100,10,10,10,10 보다
        70,70이 더 적은 최적이므로 답이 안된다


def min_coin_count(value, coin_list):
    answer =0
    while value !=0:
        if value >= coin_list[1]:
            value -=coin_list[1]
            answer+=1
            continue
        if value >= coin_list[0]:
            value -=coin_list[0]
            answer+=1
            continue
        if value >= coin_list[3]:
            value -=coin_list[3]
            answer+=1
            continue
        if value >= coin_list[2]:
            value -=coin_list[2]
            answer+=1
            continue
    
    return answer;
        
    # 코드를 작성하세요.

# 테스트
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))





##코드잇의 정답은 예술이네

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))