[LeetCode/파이썬] 322. Coin Change

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

---

알고리즘 분류

• 다이나믹 프로그래밍

문제풀이

틀린코드

def coinChanged(coins, amount):
    cnt=0
    coins.sort(reverse=True)
    while amount!=0:
        for coin in coins:
            q=amount//coin
            if q>0:
                cnt+=q
                amount-=(coin*q)
        if amount!=0:
            return -1

    return cnt

처음에 단순하게 기존 백준의 유사한 문제처럼 풀다가 틀렸다..

아이디어는 동적프로그래밍 알고리즘에서 나온다.

d[i]는 i원을 만드는데 필요한 동전의 최소 개수이다.

소스코드

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        d=[2**31-1]*(amount+1)
        d[0]=0
        for coin in coins:
            for i in range(coin, amount+1):
                d[i]=min(d[i], d[i-coin]+1)
        
        if d[amount]==(2**31-1):
            return -1
        
        return d[amount]