[LeetCode]Coin Change

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

coins과 amount가 주어지면 가장 적은 코인으로 amount를 만드는 문제입니다. 만들 수 없다면 -1을 리턴합니다.

 

처음 시도한 답안

from collections import deque


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 인덱스에 해당하는 숫자를 만들기 위해서 몇개가 필요한지 담아두는 dp
        # amount보다 1 큰값을 초기 값으로 하면 해당 인덱스(숫자)를 coin으로 만들수 없음을 표시할 수 있음
        dp = [amount+1] * (amount+1)    
        # 0을 만드는 경우는 0개가 필요하므로 0으로 설정
        dp[0] = 0

        # amount를 1씩 증가하면서 dp 갱신
        for i in range(1, amount+1):
            # 주어진 코인을 모두 사용
            for coin in coins:
                # 인덱스(숫자)보다 coin이 작은 경우에만 사용이 가능. 4를 만드는데 5코인을 사용할 순 없으니까
                if coin <= i:
                    # 현재 저장된 값과 i-coin 값에서 코인 1개를 추가하는 것중 작은것 선택
                    # (i=6이고 코인이 2라면 4를 만들기 위한 갯수 + 2짜리 코인 1개 VS 현재 저장된 dp)
                    dp[i] = min(dp[i], dp[i-coin] + 1)

        # 만들수 없었던 경우
        if dp[-1] == amount+1:
            return -1

        # 만들어진 경우
        return dp[-1]

접근 방법

1. 다이나믹 프로그래밍(DP)으로 풀이하는 문제입니다.
2. 만들어야 하는 amount 보다 1 큰값을 가지는 값으로 amount+1 만큼 dp를 생성합니다.
   1. dp에는 해당 인덱스의 amount를 만드는데 필요한 동전의 갯수가 누적됩니다.
   2. 0을 만드는 경우에는 0개가 필요하므로 dp[0]는 0으로 초기화 합니다.
3. amount 수만큼 순회합니다.
   1. 주어진 코인의 리스트를 순회합니다.
   2. 코인이 현재 인덱스보다 작은 경우에만 사용이 가능합니다. (4를 만들기 위해 5짜리 코인을 사용할수는 없습니다)
   3. 현재 저장되어있는 값과, dp[i-coin] + 1 값중 작은 값을 선택합니다.
      (i가 6이고 등장한 coin이 2라면 4를 만들기 위해 사용된 코인 + 등장한 2짜리 코인을 1개 사용의 의미입니다)
4. 만들 수 없었던 경우에는 초기값인 amount+1을 만나게 되므로 -1을 리턴합니다.
5. 만들어진 경우에는 dp[-1]을 반환합니다.

coins = [1,2,5], amount = 8인 경우의 예시를 살펴봅니다.

1. 초기 dp = [0, 9, 9, 9, 9, 9, 9, 9, 9] 로 할당합니다.
2. 인덱스가 1인 경우에는 1 코인만 사용이 가능합니다.
   
   1. min(9, dp[1-1] + 1) -> 1이 할당됩니다.
3. 인덱스가 2인 경우에는 1과 2코인 모두 사용 가능합니다.
   1. 1코인을 사용하려고 하는 경우 - min(9, dp[2-1] + 1) -> 2가 할당됩니다.
   2. 2코인을 사용하려고 하는 경우 - mint(2, dp[2-2] + 1) -> 1이 할당됩니다.
   3. 즉, 2를 만들고자 하는 경우에는 2코인 1개만 사용하면 됩니다.
4. 이런식으로 반복하면 8을 만들기위한 최소 코인수는 1,2,5로 3개이고, dp[-1]에도 3이 할당됩니다.

dp에 각 amount별로 필요한 최소 코인 갯수를 누적해나가는 것이 중요한 포인트입니다.