[LeetCode/Kotlin]Medium - 322. Coin Change

Coin Change - LeetCode

문제

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

Constraints:

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

---

풀이

나의 풀이법

풀이 접근 과정

이걸 풀기 위해 메모했던 것!!!

최종 소스코드

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

        val dp = IntArray(amount+1) { 0 }

        coins.forEach {
            if (amount >= it) dp[it] = 1
        }

        dp.forEachIndexed { i, it ->
            if (it != 1 && i != 0) {
                var min = Int.MAX_VALUE
                for (j in 1 .. i/2) {
                    if (dp[j] != 0 && dp[i-j] != 0)
                        min = min(min, dp[j]+dp[i-j])
                }
                if (min != Int.MAX_VALUE) dp[i] = min
            }
        }

        return if (dp[amount] == 0) -1 else dp[amount]
    }
}

coin을 가지고 있는 경우 해당 dp[coins] 값은 1로 둔다.

2개의 dp를 더해 하나의 dp를 만드는데, 이 경우의 최솟값을 구한다.

예를 들어 dp[4]=dp[1]+dp[3] 혹은 dp[2]+dp[2] 로 만들 수 있다.

이 때 dp[1]+dp[3]은 값이 3이고, dp[2]+dp[2]은 2 이므로 dp[4]의 값은 2가 된다.

이렇게 누적하여 amount 값까지 구해준다.

다른 풀이법

Chat GPT 추천 풀이.

import kotlin.math.min

fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0
    
    for (coin in coins) {
        for (i in coin until dp.size) {
            dp[i] = min(dp[i], dp[i - coin] + 1)
        }
    }
    
    return if (dp[amount] > amount) -1 else dp[amount]
}

이 Kotlin 코드는 동적 프로그래밍(Dynamic Programming)을 사용하여 문제를 해결합니다. dp 배열은 0부터 **amount**까지의 금액을 만들기 위한 최소 동전 개수를 저장합니다. 배열을 초기화할 때 **amount + 1**로 설정하고, 0원을 만들기 위한 최소 동전 개수는 0으로 초기화합니다. 그런 다음, 주어진 동전들을 하나씩 고려하면서 최소 동전 개수를 업데이트합니다.

마지막으로, **dp[amount]**가 초기값인 **amount + 1**보다 크면, 주어진 금액을 만들 수 없으므로 -1을 반환하고, 그렇지 않으면 최소 동전 개수를 반환합니다.

---

Comment

와… 진짜 뿌듯하다!!!

완전 내 머리에서 나왔던 dp 풀이!!

dp는 무조건 힌트를 보고 풀어야 했지만 이번엔 힌트 없이 풀어서 더 뿌듯한듯 ㅎㅎ

메모의 영향도 컸다! 메모를 하니 규칙이 눈에 확 들어와서 풀 수 있었던 것 같다 !!

재밌는 문제여뚬!!