Leetcode. Coin Change (DP, BFS)

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

Coin Change - LeetCode

 

---

 

처음 접근)

몫과 나머지, 그리고 각 변수가 사용된 개수를 활용하는 문제여서 당연히 dict지!라는 생각으로 접근을 했다

 

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        coins.sort(reverse=True)
        cal, res = {}, amount
        try:
            for i in coins:
                if amount//i != 0:
                    cal[i] = amount//i
                    res -= i*(amount//i)
                    amount %= i
            return sum(cal.values()) if res == 0  else -1
        except KeyError:
            return 0

 

 example코드를 다 통과하고 자신만만하게 submit  했지만 역시나 에러,,,,

그래서 어떤 주제의 문제를 확인했더니 Dynamic Programming과 BFS라는 키워드가 있었다..

다른 코드들을 보면서 왜 이문제가 DP인지, BFS로 풀 수 있는지 알아보려 한다 ㅜ

 

---

Dynamic Programming )

class Solution:
	def coinChange(self,coins: List[int], amount: int) -> int:
    	dp = [amount+1] * (amount+1)
        dp[0] = 0
        
        for a in range(1,amount+1):
        	for c in coins:
            	if a-c >= 0:
                	dp[a] = min(dp[a], 1+dp[a-c])
                    
        return dp[amount] if dp[amount] != amount + 1 else -1

 

coins = [1,2,5]    ;   amount = 11

a = 1, c = 1 , dp[1] = min(dp[1], 1 + dp[0]) = min(12,0) = 0

a= 1, c = 2 -> a-c가 음수로 pass

...

a = 2, c=1, dp[2] = min(dp[2], 1+dp[1]) = min(12,1) = 1

a= 2, c=2, dp[2] = min(dp[2],1+dp[0]) = min(1,1) = 1

...

a=3. c=1, dp[3] = min(dp[3], 1+dp[2]) = min(12,2) = 2

a=3. c=2, dp[3] = min(dp[3], 1+dp[1]) = min(12,1) = 1

 

a=5, c = 1, dp[5] = min(dp[5], 1+dp[4]) = min(12,12) = 12

a = 4, c = 2, dp[5] = min(dp[5], 1+dp[2]) = min(12,2) = 2

 

BFS  )

def coinChange(self, coins: List[int], amount : int) -> int:
	if amount == 0: return 0
    
    seen = set()
    count = 0
    remainders = [amount]
    
    while remainders:
    	count += 1
        temp = []
        
        for val in remainders:
        	for coin in coins:
            	rem = val - coin
                if rem ==0:
                	return count
                elif rem >0 and rem not in seen:
                	seen.add(rem)
                    	temp.append(rem)
         remainders = temp
     return -1

(왜 코드블럭 indent가 계속 에러가 나는지 모르겠네요 ㅜㅠ)

 

이 코드는 BFS를 따른 코드다

 

전체적인 구조를 봤을 때 방문여부를 나타내는 seen을 만들고 , remainders을 만든뒤, 

remainders 가 non-empty일 때 for 문을 통해 요소를 추출하고 방문여부를 체크한 뒤 temp에 더하는 방식 자체가 BFS의 전형적인 pseudocode를 따른 걸로 보인다.