[Leetcode 322] Coin Change

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

 

1. 문제설명

• coins에 들어있는 coin을 이용해서 amount 만들 때, 필요한 최소 개수
• 만들 수 없으면 -1를 반환하고 각 coin의 개수는 무한개로 가정

 

2. 문제해결

• 최소 개수를 구하는 거니까 BFS 이용
• 단, 그냥 BFS로 구현하면 메모리 초과 에러 발생
  • 가지를 뻗기 전에 cur_v와 coin을 더한 값을 방문했는지 visit을 통해 확인

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        from collections import deque
        def bfs():
            q = deque()
            visit = {}
            for coin in coins:
                q.append((1, coin))
                visit[coin] = 1
            while q:
                cur_i, cur_v = q.popleft()
                if cur_v == amount:
                    return cur_i
                elif cur_v < amount:
                    for coin in coins:
                        if cur_v + coin not in visit:
                            q.append((cur_i+1, cur_v+coin))
                            visit[cur_v+coin] = cur_i+1
            return -1
        
        if amount == 0:
            return 0
        else:
            return bfs()