[DP: Unbounded Knapsack] 518. Coin Change II ★★★★★

518. Coin Change II

 

https://hyunkookim.tistory.com/279

Knapsack 문제(배낭 문제) : DP 최적화

 

Knapsack 문제와 동전 문제의 유사점

• Knapsack 문제와 동전 문제는 모두 조합 최적화 문제이며, 동적 계획법(DP)을 사용해 해결합니다.
• Knapsack 문제:
  • 최적의 가치를 찾는 것이 목표.
  • 각 물건의 가치와 무게가 있음.
• 동전 문제:
  • 주어진 금액을 구성하는 조합의 수를 찾는 것이 목표.
  • 각 동전은 무게 대신 고유의 값(denomination)을 가짐.

 

• Knapsack 문제는 배낭의 용량 제약 조건을 만족하면서 물건의 가치를 최대화하는 문제입니다.
• 동전 문제와 Unbounded Knapsack 문제는 동전의 무한 사용 가능성에서 유사하며, DP 점화식을 활용해 효율적으로 풀 수 있습니다. 🎯

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        """
        동전 조합 문제를 해결하기 위한 점화식:
        dp[i] = dp[i] + dp[i - coin]

        점화식의 의미:
        - dp[i]: 금액 i를 만들 수 있는 동전 조합의 개수.
        - dp[i - coin]: 현재 동전을 사용하여 금액 i를 만들 때, 금액 (i - coin)을 만드는 경우의 수.
        - dp[i] += dp[i - coin]: 현재 동전으로 새로운 조합을 추가하여 dp[i]를 갱신.

        Recurrence relation:
        dp[i] = dp[i] + dp[i - coin]

        Explanation of the recurrence:
        - dp[i]: The number of combinations to make the amount i.
        - dp[i - coin]: The number of combinations to make the amount (i - coin).
        - dp[i] += dp[i - coin]: Updates dp[i] by adding the number of ways to make (i - coin), considering the current coin.
        """
        # DP 배열 초기화
        # Initialize DP array
        dp = [0] * (amount + 1)
        dp[0] = 1  # 금액 0을 만드는 방법은 아무 동전도 사용하지 않는 1가지
                  # There is one way to make amount 0, by using no coins.

        # 각 동전에 대해 DP 배열 갱신
        # Update DP array for each coin
        for coin in coins:
            for i in range(coin, amount + 1):
                # 점화식 적용: dp[i] = dp[i] + dp[i - coin]
                # Apply the recurrence: dp[i] = dp[i] + dp[i - coin]
                # - dp[i - coin]: 현재 동전을 추가하기 전의 경우의 수
                #                 Combinations before adding the current coin.
                # - dp[i]: 기존 dp[i]에 현재 동전을 추가하여 새로운 조합의 경우의 수를 누적
                #           Accumulate the new combinations using the current coin.
                dp[i] += dp[i - coin]

        # 금액 amount를 구성할 수 있는 총 경우의 수 반환
        # Return the total number of combinations for the given amount
        return dp[amount]

 

Unbounded Knapsack 문제

https://youtu.be/Mjy4hd2xgrs?si=zQoozi63_Nf8c1Ig

 

이걸로 익히자!!

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 메모이제이션을 위한 딕셔너리
        # key: (i, a) = i번째 동전부터 시작해서 현재 금액이 a일 때
        # value: 해당 상태에서 amount까지 채우는 조합 수
        dp = {}

        # dfs(i, a): i번째 동전부터 시작해서, 현재까지 만든 금액이 a일 때
        # 금액 amount를 정확히 만드는 조합의 수를 반환
        def dfs(i, total):
            """
            dfs(i, total) 함수 설명
            - i: 현재 고려 중인 동전의 인덱스 (coins[i])
            - total: 지금까지 누적된 금액
            - 목표: coins[i:] 범위 안에서, amount까지 딱 맞게 채우는 조합의 수 반환
            """

            # ✅ 종료 조건 1: 
            # 금액이 정확히 목표 amount와 같을 경우 → 정확히 목표 금액을 만든 경우 
            # → 유효한 조합 1개
            if total == amount:
                return 1

            # ✅ 종료 조건 2: 
            # 목표 금액을 초과한 경우 → 조합 불가능 
            # → 이 경로는 유효하지 않음
            if total > amount:
                return 0

            # ✅ 종료 조건 3: 
            # 동전을 전부 다 확인했지만 아직 금액이 부족함
            # → 동전을 다 사용한 경우 → 더 이상 조합 불가능
            if i == len(coins):
                return 0

            # 이미 계산한 상태면 캐시에서 꺼내서 반환
            if (i, total) in dp:
                return dp[(i, total)]

            # ------------------------------------------------------------------
            # 두 가지 선택지 중 하나를 택함:

            # 1️⃣ 현재 동전(coins[i])을 사용하는 경우 (무제한 사용 가능):
            #    - 같은 동전을 또 사용할 수 있으므로 인덱스 i는 그대로 유지
            #    - 현재 금액에 coins[i]를 더해서 다음 단계로 진행
            use_it = dfs(i, total + coins[i])

            # 2️⃣ 현재 동전을 사용하지 않고 다음 동전으로 넘어가는 경우:
            #    - 다음 동전으로 넘어가야 하므로 i+1
            #    - 현재 금액은 그대로 유지
            skip_it = dfs(i + 1, total)

            # 두 경우의 결과를 더해서 캐시에 저장
            dp[(i, total)] = use_it + skip_it
            return dp[(i, total)]

        # 시작: 인덱스 0번 동전부터, 금액 0에서 시작
        return dfs(0, 0)

 

📌 핵심 요약

조건	의미
total == amount	목표 금액 정확히 도달 → 유효한 조합 1개
total  > amount	초과함 → 불가능한 조합
i == len(coins)	동전을 다 썼는데도 금액이 부족 → 불가능
dfs(i, total  + coins[i])	현재 동전을 계속 사용하는 경우
dfs(i + 1, total)	현재 동전을 건너뛰고 다음 동전으로 넘어가는 경우

---

💡 이 방식이 좋은 이유

• 중복 조합 제거: 같은 금액을 여러 경로로 만드는 경우를 캐싱해서 재계산 방지
• 동전 순서를 고정한 DFS이기 때문에 **조합(Combination)**만 카운트됨
  → 즉, [1, 2]와 [2, 1]은 같은 조합으로 취급됨

 

---

더 빠르게

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [[0] * (len(coins) +1) for i in range(amount+1)]
        dp[0] = [1]*(len(coins) +1)

        for a in range(1, amount+1):
            for i in range(len(coins) -1, -1, -1):
                dp[a][i] = dp[a][i+1]
                if a - coins[i] >=0:
                    dp[a][i] += dp[a-coins[i]][i]
        return dp[amount][0]

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1

        for i in range(len(coins)-1, -1, -1):
            for a in range(1, amount+1):
                if a-coins[i] >=0:
                    dp[a] += dp[a-coins[i]]
        return dp[amount]

 

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1

        for coin in coins:
            for a in range(1, amount+1):
                if a-coin >=0:
                    dp[a] += dp[a-coin]
        return dp[amount]

 

loop 가 coins -> amount 순서 이면,

- coin의 중복 조합은 1개로 고려하는 코드로 되고

- (2,1,1), (1,2,1), (1,1,2) => 1개로..

 

loop 가 amount -> coins 순서 이면,

- coin의 중복 조합은 여러개로 counting

- (2,1,1), (1,2,1), (1,1,2) => 3개로..