[Leetcode] 322. Coin Change

21-11-28
sovled with hint

Problem

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.

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

Solution

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        if amount==0:
            return 0
        
        dp=[int(2e9)]*(amount+1)
        que=deque()
        
        for coin in coins:
            if coin > amount:
                continue
            elif coin==amount:
                return 1
            
            dp[coin]=1
            que.append(coin)
        
        while que:
            #print(dp)
            cur = que.popleft()
            
            for coin in coins:
                if cur+coin>amount:
                     continue
                elif cur+coin==amount:
                    return dp[cur]+1
                
                if dp[cur+coin]>dp[cur]+1:
                    dp[cur+coin]=dp[cur]+1
                    que.append(cur+coin)
                
                    
        return -1

처음에 안 풀리다가, 저녁 먹고 와서, 문제 분류가 dynammic programming인 것을 보고 힌트를 얻어 풀었다.
처음에는 amount에서 출발해 greedy 문제처럼 숫자가 큰 코인으로 처리하려고했다. 하지만 코인 구성이 n진법을 구성하는 숫자 조합이 아니라 greedy가 안 된다. greedy로 했을 때는, amount에서 금액을 차감하는 식으로 구현했다. 그래서 DP를 봤을 때, 생각 흐름을 바꾼다고 시간이 걸렸다.

DP로 풀때는, 내가 만들 수 있는 금액을 작은 금액부터 목표 금액까지 계속 더해나간다.
dp[i]는 i원을 만들 때 필요한 최소 코인 수이다.

What I tried first

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        global ans
        if amount==0:
            return 0
        coins.sort(reverse=True)
        
        l=len(coins)
        print(coins)
        def goDFS(i,num,amnt):
            global ans
            #print(i,num,amnt)
            if i==l:
                return 
            
            value=coins[i]
            
            share,remain=divmod(amnt,value)
            
            if remain==0:
                #print(num+share)
                if ans>num+share:
                    ans=num+share
                return
                
            
            for j in range(share,-1,-1):
                goDFS(i+1,num+j,amnt-j*value)
                    

                
        
        ans=int(2e9)
        
        goDFS(0,0,amount)

        
        
        if ans==int(2e9):
            return -1
        return ans

amount에서 coin을 차감하는 식으로 recursion을 이용해 풀려고했다. 하지만 recursion하는 경우의 수가 너무 많아져 시간 초과가 발생했다. 처음에 greedy라고 생각했다가, 틀리고 고치는
과정에서 생각의 흐름이 그렇게 자연스럽게 흘러갔다.