박종훈 알고리즘 블로그

(Leetcode) 322 - Coin Change

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

DP 문제이다.

내가 풀었던 방식

처음 생각

처음에는 큰 동전부터 넣어서 될 때까지 하면 베스트 일 것이라고 생각했다. 하지만 그렇게 간단하지는 않았다.

예를들어 [100, 30, 1] 이라는 동전이 있다고 해보자. 이때 주어지는 amount는 120 이라고 하면

30으로는 4개면 되지만 100을 먼저 채우면 30은 들어갈 수 없고 1짜리 20개를 더 써서 21개의 동전이 사용된다.

중간 생각

그래서 모든 경우의 수를 다 찾아봐야 겠다고 생각했다.
처음에는 잘 먹히는 듯 보였으나, 역시나 복잡한 경우로 인해 타임아웃이 발생되었다.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0

        coins.sort()
        coins.reverse()

        stack = []
        worst = math.floor(amount / coins[-1])
        min = worst + 1

        def calc(index, amount):
            nonlocal min
            # print("start:", stack, len(stack), amount, index)
            if len(stack) == worst:
                return -1 if min > worst else min

            while index == len(coins):
                last_removed_index = stack.pop()
                amount += coins[last_removed_index]
                index = last_removed_index + 1

            while amount > 0:
                stack.append(index)
                amount -= coins[index]

            if amount == 0:
                if min > len(stack):
                    min = len(stack)
                    # print("min:", min)

            removed_index = stack.pop()
            amount += coins[removed_index]
            return calc(removed_index + 1, amount)

        try:
            return calc(0, amount)
        except:
            return min

모범 답안

모든 시점에서의 최선을 상황을 찾는다.

from typing import List
import math


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

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

예시를 들어 차근차근 실행시켜보기

for 문의 끝에 아래와 같이 print를 넣어주면 다음과 같이 print 된다.

print(solution.coinChange([1, 2, 5], 10))
[0, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf] 1
[0, 1, 1, inf, inf, inf, inf, inf, inf, inf, inf] 2
[0, 1, 1, 2, inf, inf, inf, inf, inf, inf, inf] 3
[0, 1, 1, 2, 2, inf, inf, inf, inf, inf, inf] 4
[0, 1, 1, 2, 2, 1, inf, inf, inf, inf, inf] 5
[0, 1, 1, 2, 2, 1, 2, inf, inf, inf, inf] 6
[0, 1, 1, 2, 2, 1, 2, 2, inf, inf, inf] 7
[0, 1, 1, 2, 2, 1, 2, 2, 3, inf, inf] 8
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, inf] 9
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2] 10

풀어서 설명하면 다음과 같다.

example page1 example page2 example page3 example page4 example page5

시간복잡도

  • 이중 반복문 사용
    • 바깥쪽 반복문 : amount 만큼 반복 (O(n))
    • 안쪽 반복문 : coins 리스트의 length 만큼 반복 (O(m))

O(n * m) 의 시간 복잡도를 가짐

공간복잡도

amount 만큼 dp array를 생성함

O(n) 의 공간 복잡도를 가짐

결론

DP 문제를 더 많이 접해봐야겠다는 생각이 들었다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , DP , coin