[LeetCode] 322. Coin Change (Python)

 

난이도: Medium

문제 설명

---

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

 

문제 예제

---

Example 1:

Input: coins = [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] <= 2^31 - 1
• 0 <= amount <= 10^4

 

✏️ Solution(솔루션)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        dp = [float('inf') for _ in range(amount+1)]

        for i in range(1, amount+1):
            if i in coins:
                dp[i] = 1
            else:
                for coin in coins:
                    if i-coin > 0:
                        dp[i] = min(dp[i], dp[i-coin] + dp[coin])

        return dp[-1] if dp[-1] != float('inf') else -1

 

 

처음에는 아래와 같이 문제를 풀었는데 Time Limit Exceeded가 발생했다.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0 for _ in range(amount+1)]

        for i in range(1, amount+1):
            if i in coins:
                dp[i] = 1
            else:
                temp = float('inf')
                for j in range(1, i):
                    temp = min(temp, dp[j] + dp[i-j])
                dp[i] = temp
        
        return dp[-1] if dp[-1] != float('inf') else -1

 

아마 for j in range(1,i): 반복문 때문일 것 같았다.

 

저 반복문을 돌린 이유는 만약 i가 coins에 없는 수이면서 6이라고 할때, 6을 만들 수 있는 최소의 수를 찾기 위해서 였다

ex) dp[i] = min(dp[1] + dp[5], dp[2] + dp[4], + dp[3] + dp[3])

 

하지만, i 값이 커지게 되면서 시간초과가 뜨는 것 같았다.

 

그래서 생각해보니 굳이 1부터 i까지 돌리 필요 없이 coins에 있는 수만 고려하면 될 것같았다.

그리고 coins의 최대 길이는 12이기 때문에 시간에 많은 영향도 없을 것 같았다.

 

그래서 다음과 같이 코드를 수정하고 정답을 맞출 수 있었다.

for coin in coins:
	if i-coin > 0:
		dp[i] = min(dp[i], dp[i-coin] + dp[coin])

---

문제: 322. Coin Change

 

깃허브: github

algorithm_practice/LeetCode/322-coin-change at main · laewonJeong/algorithm_practice