(LeetCode) Coin Change with Python

Coin Change

 

You are given coins of different denominations and a total amount of money amount.

: 다른 종류의 동전과 총 금액이 주어진다.

Write a function to compute 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.

: 그 금액을 동전의 조합으로 만들 수 없으면 -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

 

Example 4:

Input: coins = [1], amount = 1
Output: 1

 

Example 5:

Input: coins = [1], amount = 2
Output: 2

 

Constraints:

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

 

💯 Solution

동적계획법을 사용해서 작성한다.

최종적으로 반환해야하는 값은 amount를 구성하기 위해서 사용한 "최소" coins의 갯수를 구하면 된다.

만약, 없다면 -1을 반환하면 된다.

(총 금액이 만약 0이라면, 0을 반환)

 

class Solution():
    def coinChange(self,coins:List[int],amount:int) -> int:
        """
           :type coins: List[int]
           :type amount: int
           :rtype: int
       """
        # 임의의 가장 큰값을 만든다
        dp=[float('Inf')]*(amount+1)
        # 0번째 값은 0으로 초기화
        dp[0]=0
        # coins를 오름차순 정렬
        coins.sort()
 
        for i in range(1,amount+1):
            #print('i는:',i)
            # 임의의 큰 값으로 temp 설정
            temp=[float('Inf')]
            #print(temp)
            for c in coins:
                #print('c는:',c)
                # i가c보다 작다면
                if i-c<0:
                    break
                temp.append(dp[i-c])
            dp[i]=min(temp)+1
            print(dp)
        return dp[amount] if dp[amount] != float('Inf') else -1

- dp[amount] : amount를 충족시킬 수 있는 코인의 최소 갯수

- 1~amount까지의 반복문을 임의로 만든다. => dp=[float('Inf')]*(amount+1)

- dp[0[]은 0으로 측정

- for문으로 amount 를 1부터 amount까지 꺼내기 

- 임의의 리스트 : temp 를 만들고 가장 큰 값으로 배정

- coins 를 하나씩 뽑아서, amount와 비교 / 만약, amount가 coin보다 작다면 break 로 for문 종료 (for문 돌 필요가 없음)

- amount가 coin보다 크다면, 임의의 리스트 temp에 dp[i-c] 를 추가

- dp[amount] 값은 임의로 만든 temp 리스트에 최소값에 +1을 한다.

- if문이 참이라면 dp[amount]를 반환하고 참이 아니라면 -1을 반환한다.