[LeetCode] 322. Coin Change - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

각각 다른 금액의 동전이 담긴 정수 배열 coins와 총 금액을 나타내는 정수 amount가 주어질 때, 해당 금액을 구성하는 데 필요한 동전의 최소 개수를 return 하는 문제이다. 각 종류의 동전은 무한히 있다고 가정한다(같은 종류의 동전을 여러 번 사용할 수 있다). 동전의 어떤 조합으로도 그 금액을 채울 수 없으면 -1을 return 한다.

Example 1)
Input: conis = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2)
Input: coins = [2], amount = 3
Output: -1

Example 3)
Input: coins = [1], amount = 0
Output: 0

제한사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

문제 풀이

성공 코드

from typing import List
from math import inf

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        max_cost = inf
        dp_array = [-1] * (amount+1)
        dp_array[0] = 0
        
        for idx in range(amount+1):
            if dp_array[idx] != -1:
                continue
            
            crnt_min = max_cost
            for coin in coins:
                last_idx = idx - coin
                if last_idx < 0:
                    continue
                last_cost = dp_array[last_idx]
                if last_cost == -1:
                    continue
                cost = last_cost + 1
                crnt_min = min(cost,crnt_min)
                
            dp_array[idx] = -1 if crnt_min==max_cost else crnt_min
            
        return dp_array[amount]

시간 복잡도 : O(k*n)

k는 동전의 개수를 의미한다. n은 amount를 의미한다.

공간 복잡도 : O(n)