동전교환

main.py

"""
# 문제 : 동전 교환

각기 다른 액면을 가진 동전 배열과 거슬러주어야 하는 총 금액을 입력으로 받으면 잔도의 조합으로 거스름돈을 맞춰주기 위한 최소한의
동전 개수를 반환하자.

예를 들어서 [1, 5, 10, 25] 액면의 동전이 있다고 할 때, 거스름돈이 1이라면 액면 1인 동전 하나만 있으면 된다.

### 아이디어 (Brute-Force)

1. 거스름돈 총액이 0이면 0을 반환한다.
2. 최소 개수(비교를 위함)를 최대값(float('inf'))으로 설정한다.
3. coins (동전 배열을 순회한다.)
  - amount가 현재 coin 보다 크다면 재귀 호출로 amount - coin 하여 호출한다.
  - 재귀 호출의 복귀로 호출 개수를 반환한다. 반환된 값이 현재 순회에서 최소 개수와 비교하여 더 작은 값으로 업데이트
3. 최소 개수 + 1을 반환한다.

### 아이디어 (동적 프로그래밍 - Top Down)

1. 총액 크기 만큼 배열을 생성한다. (-1로 초기화)
  - 각 인덱스는 0부터 총액 (amount)까지
2. dp[amount]가 -1이 아니면 바로 반환한다.
3. 동전 액면만큼 순회한다.
  - 현재 amount가 동전 액면보다 크면 동전 액면을 amount에서 빼고 재귀 호출
  - 재귀 호출의 복귀로 호출 개수를 반환한다. 반환된 값이 현재 순회에서 최소 개수와 비교하여 더 작은 값으로 업데이트
4. dp[amount]에 최소 개수 + 1 하여 더하고 해당 값을 반환한다.

### 아이디어 (동적 프로그래밍 - Bottom Up)

1. 총액 크기 만큼 배열 생성 (-1로 초기화)
  - 각 인덱스는 0 ~ 총액 (amount) 까지
2. 0에서 총액만큼 순회한다.
  - 액면 크기를 순회
  - dp[a - coin[c]]와 dp[i]와 비교하여 작은 값으로 dp[a]를 업데이트
3. dp[amount]를 반환

"""
from typing import List


def coin_change(coins: List[int], amount: int) -> int:
    def coin_recur(remain: int):
        nonlocal coins

        if remain == 0:
            return 0

        min_coins = float('inf')
        for coin in coins:
            if remain >= coin:
                curr_min = coin_recur(remain - coin)
                min_coins = min(curr_min, min_coins)
        return min_coins + 1

    return coin_recur(amount)


def coin_change2(coins: List[int], amount: int) -> int:
    dp = [-1 for _ in range(amount + 1)]

    def coin_recur(remain: int):
        nonlocal dp, coins
        if remain == 0:
            return 0

        if dp[remain] != -1:
            return dp[remain]
        min_coin = float('inf')

        for coin in coins:
            if remain >= coin:
                min_coin = min(min_coin,
                               coin_recur(remain - coin) + 1)
        dp[remain] = min_coin
        return dp[remain]

    return coin_recur(amount)


def coin_change3(coins: List[int], amount: int) -> int:
    dp = [float('inf') for _ in range(amount + 1)]

    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i - coin] + 1, dp[i])

    return dp[amount]


if __name__ == "__main__":
    coins = list(map(int, input().split()))
    amount = int(input())

    print(coin_change3(coins, amount))