[4코3파] #287. Leetcode 322. Coin Change

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (287일차)
[4코1파] 2023.01.13~ (279일차)
[4코3파] 2023.10.01 ~ (17일차)

Today :

2023.10.17 [287일차]

322. Coin Change

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

문제 설명

동전을 나타내는 정수 배열 coin과 총 금액을 나타내는 정수 금액이 주어질 때,
총 금액을 아나태는 금액을 구성하는데 필요한 최소 동전의 개수를 반환하는데,
해당 총 금액을 조합으로 나타낼 수 없으면 -1을 반환함

문제 풀이 방법

dfs의 tree로 해당 총 금액의 조합을 그려보면서,
bottom-up인 tabulation 방법인 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

증빙

여담

우짜노 dp 는 들어도 들어도 모르겠는데,,
그렇다면 또 들어!