(LeetCode) 322. Coin Change

322. Coin Change

• Explore : Interview > Top Interveiw Questions > Medium Collection
• 분류 : Dynamic Programming
• 난이도 : Medium

Problem

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

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

Solution

Exapnder

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        if (amount == 0) {
            return 0
        }

        var dp = IntArray(amount + 1) { Int.MAX_VALUE - 1}

        dp[0] = 0

        for (i in 1 .. amount) {
            coins.forEach {
                if (it <= i) {
                    dp[i] = Math.min(dp[i], dp[i - it] + 1)
                }
            }
        }

        return if (dp[amount] == Int.MAX_VALUE - 1) {
            -1
        } else {
            dp[amount]
        }
    }
}

Point of Thinking

• 주어진 amount보다 1만큼 더 크게, index가 특정 금액을 의미하고, 값은 동전 갯수를 의미하는 dp 배열을 생성한다.
• dp 배열은 주어진 최대 표헌범위인 2^31 - 1로 세팅한뒤, 0원을 만들땐 동전이 필요가 없으므로, dp[0] = 0으로 초기값을 부여한다.
• 현재 계산하려는 목표 금액이 i원이라면 dp[i]의 값과 주어진 코인들을 하나씩 빼가면서 카운트를 올려준다.
• 계산후 dp[amount]가 초기값인 2^31 -1이라면 불가능한 케이스이므로 -1을, 아니라면 계산된 값을 반환하면 Accepted.