[Python] LeetCode - Coin Change

https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

* 문제해석: 주어진 coins배열의 동전들을 가지고 amount에 해당하는 값을 만들 때, 필요한 동전의 

                   최소 갯수를 return, 만들 수 없으면 -1 return

 

# DP문제이다. Greedy문제인 '거스름돈 문제'와 비슷해 보이지만, 이 문제는 coins의 동전들이 다른 동전의 

   배수가 아닐 수 있으므로(배수인 경우도 있다.) Greedy로 접근하면 안되고 DP로 해결해야 한다.

 

1. 우선 amount + 1칸의 dp배열을 만들고 -1을 넣어준다. (dp[0] = 0)

 

2. 0부터 amount까지 반복문을 돌며 만약 dp[idx]가 -1이 아니라면, 이미 그 값을

    구한 상태이므로 continue한다.

   

3. coins에 있는 동전들 i에 대하여 idx - i가 0보다 작거나 dp[idx - i]가 -1이면 idx-i원에 해당하는 동전을

   사용하지 못하므로 continue해준다. (x가 idx - i이다)

 

4. m에 m과 dp[idx - i] + 1 중 최솟값을 넣어준다.

 

5. 10 ~ 14줄의 반복문을 빠져나간뒤 m이 987654321이라면 m이 갱신되지 않았으므로 모든 동전을

   사용해도 idx원을 만들 수 없는 경우이므로 dp[idx]에 -1을 넣어주고, 아니라면 m을 넣어준다.

 

6. amount원을 만드는 동전의 최소 갯수인 dp[amount]을 return해준다.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [-1] * (amount + 1)
        dp[0] = 0
        
        for idx in range(amount + 1):
            m = 987654321
            if dp[idx] != -1:
                continue
            for i in coins:
                x = idx - i
                if x < 0 or dp[x] == -1:
                    continue
                m = min(m, dp[x] + 1)
    
            dp[idx] = -1 if m == 987654321 else m
        
        return dp[amount]

# 만약 coins = [2, 3, 5]이고 amount가 11이라면

   dp[11] = min(dp[11 - 2], dp[11 - 3], dp[11 - 5]) + 1 이고

   dp[9] = min(dp[9 - 2], dp[9 - 3], dp[9 - 5]) + 1

                          .

                     .

                     .

  이런식으로 진행이 된다.