[Leetcode/파이썬] 322. Coin Change

Coin Change

---

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

 

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

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

        return dp[amount] if dp[amount] != 1<<32 else -1

힌트에 DP와 BFS가 있길래 고민하다가 DP로는 푼 기억이 있어서 푼거 보고 다시 풀어보았다. 그럼 BFS로는 어떻게 풀지는 다음에... 생각해보자.

이런 문제를 맞닥뜨리게 되면 저 amount를 어디에 둘지를 고민해보아야 한다. 이 문제는 amount를 인덱스에 두는 방법이다. DP 테이블을 amount의 갯수만큼 만들어서 0~amount까지 접근이 가능하도록 한다. (amount + 1 개 만큼 만들면 된다.) 

그런 다음 현재의 코인 갯수를 DP테이블 값에 넣으면 되는데, 우리는 가장 적은 코인 갯수로 가져갈 것이기 때문에 가장 큰 숫자로 초기 값을 잡은 후 가장 첫번째인 0번 인덱스는 0으로 초기화를 한다. 

이중 for문을 돌면서 코인을 하나씩 쌓아간다. curr - coin == 0 이면 0번 인덱스인 0값을 가져와서 +1 한다. 이를 반복하다보면 현재 값에는 가장 적은 수의 코인이 남게 된다.

생각보다 어려워서 다시 한 번 봐야겠다.