4.4.3

main.py

"""
문제 4.4.3 동전 교환

가게에 가서, 물건을 사고 물건 값을 지불하고 남은 잔돈을 거슬로 주는 과정을 코딩하는데
가장 적은 개수의 동전으로 반환해야하는 것이 문제이다. 잔돈으로 거슬러 주는 동전의 값을
배열로 입력 받는데, 예를 들어 [1, 2, 5] 이고 거슬러줘야 하는 돈이 11이라면 [5, 5, 1] 로 3개를
거슬러 주는 것이 가장 적은 동전의 개수로 반환한 것이다.
"""
import sys
from typing import List


def coinChange(coins: List[int], value: int) -> int:
    def change(v: int):
        if v == 0:
            return 0
        min_coin_cnt = sys.maxsize
        for c in coins:
            if v - c >= 0:
                change_cnt = change(v - c)
                if change_cnt < min_coin_cnt:
                    min_coin_cnt = change_cnt
        return min_coin_cnt + 1

    ans = change(value)

    return ans if ans != sys.maxsize + 1 else -1


if __name__ == '__main__':
    coins = list(map(int, input().split()))
    value = int(input())
    print(coinChange(coins, value))