Coin Change | LeetCode 809 | Python3 🐍

 

📄 목차

• 🤔 문제 : Coin Change | LeetCode 780
• 💡 풀이
  • 1. Top Down 
  • 2. Bottom Up

 

 

🤔 문제 : Coin Change | LeetCode 780

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/809/

동전을 조합하여 가장 적은 동전 조합으로 주어진 금액을 만드는 문제입니다. 

전형적인 Dynamic Programming 문제네요.

 

Dynamic Programming

1. 큰 문제는 작은 문제로 나누어 푼다

2. 작은문제에서 푼 정답은 기억해두었다가 동일한 문제가 나오면 그대로 활용한다.

 

 

💡 풀이

1. Top Down 

amount에서 동전만큼씩 깎아내려가는 방식입니다.

dp라는 함수를 recursive하게 호출하게 됩니다. 

from typing import List
from functools import lru_cache
import math

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not coins: return -1
        INF = math.inf
        @lru_cache(None)
        def dp(n):
            if n < 0: return -1
            if n == 0: return 0
            ans = INF
            for c in coins:
                if dp(n-c) >= 0:
                    ans = min(ans, dp(n-c)+1)
            return ans
        return dp(amount) if dp(amount) < INF else -1

 

- @lru_cache

python에서는 memoization대신 cache를 활용할 수 있습니다. 

@lru_cache 데코레이터를 활용하면 해당 함수에 대한 결과값을 캐싱됩니다. 

즉, 한 번 계산한 값은 다시 계산하지 않고 캐싱된 값을 그냥 가져옵니다. 

 

- 예시

Input: coins = [3, 5], amount = 8

이 경우에 dp가 어떻게 호출되는지 생각해보겠습니다.

 

dp$8$ : min$1, 1$+1 = 2

- 3, 5를 뺀 값에 대해 각각 dp 호출

- dp$5$ : min$0, INF$ +1 = 1

   - 3, 5를 뺀 값에 대해 각각 dp 호출  -> 0이상인 값 중 min값 

   - 1) dp$5-3$ : dp$2$ = INF

        - 3, 5를 뺀 값에 대해 각각 dp 호출 -> 0이상인 값 중 min값 

        - dp$-1$ = -1

        - dp$-3$ = -1

    -2) dp$5-5$ : dp$0$ = 0

- dp$3$ : 0 + 1 = 1

   - 3, 5를 뺀 값에 대해 각각 dp 호출  -> 0이상인 값 중 min값 

   - 1) dp$3-3$ : dp$0$ = 0

    -2) dp$3-5$ : dp$-2$ = -1

 

 

2. Bottom Up

0에서부터 amount까지 올라가며 몇개의 동전이 필요한지 구하는 방식입니다. 

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = math.inf
        dp = [0]+[-1]*amount
        for i in range(min(coins), amount+1):
            # print(i, [i-c for c in coins if i-c >= 0 and dp[i-c] >= 0])
            dp[i] = min((dp[i-c] for c in coins if i-c >= 0 and dp[i-c] >= 0), default=-2)+1
        return dp[amount]

 

- 예시

Input: coins = [3, 5], amount = 8

이 경우에 Bottom-up 방식으로는 dp 배열이 어떻게 채워질까요?