[DP: Unbounded Knapsack] 322. Coin Change

322. Coin Change

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 메모이제이션을 위한 딕셔너리
        # dp[amount] = 해당 금액을 만드는 최소 동전 수
        dp = {}
        
        # dfs(amount): 해당 금액을 만들기 위한 최소 동전 개수를 반환
        def dfs(amount):
            # 금액이 0이면 동전이 필요 없음 → 종료 조건
            if amount == 0:
                return 0

            # 이미 계산한 금액이면 캐시에서 바로 반환
            if amount in dp:
                return dp[amount]
            
            # 최소 동전 수를 무한대로 초기화 (비교용)
            res = float("inf")

            # 각 동전을 하나씩 시도해 보기
            for coin in coins:
                # 동전을 사용할 수 있는 경우에만 (음수 방지)
                if amount - coin >= 0:
                    # 1개를 사용하고, 나머지 금액에 대해 dfs 호출
                    res = min(res, 1 + dfs(amount - coin))

            # 현재 금액에서 최소 동전 수를 캐시에 저장
            dp[amount] = res
            return res

        # amount 금액을 만들기 위한 최소 동전 수 계산
        minCoins = dfs(amount)

        # 만약 만들 수 없는 경우 (무한대가 남아있다면) → -1 반환
        return -1 if minCoins == float("inf") else minCoins

 

🧠 핵심 요약

요소	의미
dfs(amount)	현재 금액을 만들기 위한 최소 동전 수
res = float("inf")	아직 답을 못 찾았다는 의미로 무한대 사용
1 + dfs(amount - coin)	현재 동전 1개 사용 + 나머지 금액 재귀 탐색
dp[amount]	중복 계산을 막기 위한 메모이제이션

---

📌 예시

coins = [1, 2, 5], amount = 11

• 가능한 경우:
  • 5 + 5 + 1 → 총 3개
• 정답: 3

https://youtu.be/H9bfqozjoqs