[LeetCode] 322. Coin Change (medium, python)

https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

BFS 풀이

from collections import deque
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)

        if amount % coins[0] == 0:
            return amount // coins[0]

        queue = deque() 
        queue.append((0, 0)) #현재까지의 값, 갯수
        visited = set()
        while queue:
            now_amount, cnt = queue.popleft()
            if now_amount == amount:
                return cnt
            if now_amount in visited:
                continue
            visited.add(now_amount)
            for c in coins:
                if now_amount + c <= amount:
                    queue.append((now_amount + c, cnt + 1))
        
        return -1

visited로 큰 수로 이미 만든 수 인 경우 탐색을 멈추게하였다. 

DP 풀이

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

        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] = min(dp[i], dp[i-coin] + 1)
        
        return dp[amount] if dp[amount] < amount +1 else -1

 

둘 다 시간복잡도는 O(coins*amount) 이다.

visited로 반복연산 제거 안해주면 O(coins^amount)