322. Coin Change

322. Coin Change

 

https://youtu.be/H9bfqozjoqs?si=WXXZLGYu8Q1PKHbY

 

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp 개수: 0~amount 까지, 따라서, amount+1 개 생성
        # dp[amount]: amount 만드는데 필요한 최소 동전 개수
        dp = [amount+1] * (amount+1) 
        dp[0] = 0

        # 모든 금액에 대해서 최소 동전개수 계산
        for a in range(1, amount+1): # dp[amount] 까지
            for c in coins:
                if a-c >=0: 
                    dp[a] = min(dp[a], 1 + dp[a-c])
                
        return dp[amount] if dp[amount] != amount+1 else -1

 

GPT

문제를 DFS + 백트래킹으로 해결하기

DFS + 백트래킹으로 이 문제를 해결하려면, 가능한 모든 동전 조합을 탐색하면서 최소 동전 개수를 찾는 방식으로 구현할 수 있습니다. 하지만, 이 방식은 탐색 범위가 매우 크기 때문에 작은 입력에서는 잘 동작하지만 큰 입력에서는 비효율적일 수 있습니다.

---

DFS + 백트래킹 풀이

아이디어

1. 각 동전 선택에 대해 다음 상태를 재귀적으로 탐색합니다.
2. 현재까지 사용한 동전의 개수를 추적하며, 목표 금액(amount)에 도달했을 때 최소값을 갱신합니다.
3. 재귀를 사용하여 모든 조합을 탐색합니다.
4. 이미 목표 금액을 초과한 경우 더 이상 탐색하지 않도록 가지를 친다 (백트래킹).

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # greedy
        # 브루포스: DFS - Backtracking
        self.min_coin_cnt = float('inf')
        def dfs(remain, count):
            if remain == 0: # 목표 금액에 도달
                self.min_coin_cnt = min(self.min_coin_cnt, count)
                return
            if remain < 0:
                return 
            
            for coin in coins:
                dfs(remain-coin, count+1)

        dfs(amount, 0)

        return self.min_coin_cnt if self.min_coin_cnt != float('inf') else -1

 

테스트 케이스는 통과하나,

제출하면, Time Limit Exceeded

 

주의

• 이 풀이는 브루트 포스 접근법이며, 입력 크기가 커질수록 비효율적입니다.
• 더 효율적인 방법은 **동적 프로그래밍(DP)**를 사용하는 것입니다.

그래서, DP로...

 

문제를 동적 프로그래밍(DP)으로 해결하기

DP를 사용하면 중복 계산을 방지하고, 문제를 더 효율적으로 해결할 수 있습니다.

---

DP 풀이 아이디어

1. dp[i]의 정의: 금액 i를 만드는데 필요한 최소 동전 개수.
   • 초기값: dp[0] = 0 (금액 0을 만드는데 동전이 필요 없음).
   • 나머지는 매우 큰 값(float('inf'))으로 초기화.
2. 점화식:
   • 각 동전 coin에 대해 dp[i] = min(dp[i], dp[i - coin] + 1):
     • i를 만들기 위해 coin을 사용하는 경우와 사용하지 않는 경우 중 최소값을 선택.
3. 결과 반환:
   • dp[amount]가 초기값 그대로이면, 해당 금액을 만들 수 없으므로 -1 반환.
   • 그렇지 않으면 dp[amount] 반환.

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # DP 배열 초기화: 0부터 amount까지
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # 금액 0을 만드는 데 필요한 동전 개수는 0
        
        # 모든 금액에 대해 최소 동전 개수 계산
        for i in range(1, amount + 1):  # 1부터 amount까지 순회
            for coin in coins:  # 각 동전 사용
                if i - coin >= 0:  # 현재 금액에서 동전을 뺀 값이 0 이상일 때
                    dp[i] = min(dp[i], dp[i - coin] + 1)  # 최소값 갱신
        
        # dp[amount]가 초기값이면 금액을 만들 수 없음
        return dp[amount] if dp[amount] != float('inf') else -1

 

DP의 장점

• 중복 계산을 방지하여 효율성을 높임.
• 입력 크기가 커져도 비교적 빠르게 결과를 얻을 수 있음.

 

dp[i] = min(dp[i], dp[i - coin] + 1)

에서 **1을 더하는 이유**는,

현재 금액 i를 만들기 위해 새로운 동전 하나(coin)를 추가로 사용했기 때문

 

구체적인 설명

dp[i - coin] 의 의미

• dp[i - coin]은 i - coin이라는 금액을 만들기 위해 필요한 최소 동전 개수입니다.
• 예를 들어, i = 7이고 coin = 2인 경우, dp[5]는 금액 5를 만들기 위한 최소 동전 개수를 의미합니다.

+1의 의미

• 금액 i - coin에서 coin 하나를 더 추가하면 금액 i를 만들 수 있습니다.
• 즉, dp[i - coin]까지는 이전 상태에서 만든 것이고, 새로 추가된 coin 때문에 1개의 동전을 추가한 것입니다.

요약

• +1은 새로운 동전을 추가하는 동작을 나타냅니다.
• 이 점화식은 현재 금액을 만들기 위해 사용하는 최소 동전 개수를 계속 갱신합니다.
• 최종적으로 dp[amount]에 최소 동전 개수가 저장됩니다.

최종!!

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
    	"""
        # dp 개수: 0~amount 까지, 따라서, amount+1 개 생성
        # dp[amount]: amount 만드는데 필요한 최소 동전 개수
        """
        dp = [float('inf')] * (amount+1) 
        dp[0] = 0

        # 모든 금액에 대해서 최소 동전개수 계산
        for i in range(1, amount+1): # dp[amount] 까지
            for coin in coins:
            	"""
                # 현재 금액 i 를 coin 갖고 만들어야 하니,
                # i-coin 이 0 이상(0포함) 이면, 
                # 현재 dp[i]: 무한대 와 이전 i-coin 만든 개수와 현재 개수 와 최소값 구해서.
                # 그런데, i 는 고정해놓고, coin 이 다른 것도 비교하니,
                # 이전 다른 dp[i] 와도 비교해서, 최소값 찾음
                """
                if i-coin >=0: 
                    dp[i] = min(dp[i], dp[i-coin] + 1)
                
        return dp[amount] if dp[amount] != float('inf') else -1

 

DFS로..

 

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # memoization
        dp = {}

        def dfs(remain):
            if remain in dp:
                return dp[remain]
            
            # 남은 금액이 0이면 동전이 필요하지 않으므로
            if remain == 0: 
                return 0
            
            # 남은 금액이 음수이면. 불가능한 조합이므로, -1 반환
            if remain < 0:
                return -1

            min_coins = float("inf")  # 최소 동전 개수를 저장할 변수

            # 모든 동전에 대해서 재귀적으로 탐색
            for coin in coins:
                coin_count = dfs(remain-coin)

                if coin_count != -1: # 유효한 조합이 있는 경우
                    min_coins = min(min_coins, coin_count + 1) # +1은 현재 동전 고려

            dp[remain] = min_coins if min_coins != float("inf") else -1
            return dp[remain]

        return dfs(amount)