[백준 2294번] 동전 2 - Kotlin

[백준 2294번] 동전 2 - Kotlin

https://www.acmicpc.net/problem/2294

---

문제

• n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.
• 그러면서 동전의 개수가 최소가 되도록 하려고 한다.
• 각각의 동전은 몇 개라도 사용할 수 있다.

---

입력

• 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
• 동전의 가치는 100,000보다 작거나 같은 자연수이다.
• 가치가 같은 동전이 여러 번 주어질 수도 있다.

---

출력

• 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

---

풀이

import kotlin.math.min

private class Solution2294 {
    fun solution(k: Int, coins: IntArray): Int {
        coins.sort()

        val dp = IntArray(k + 1) {
            when (it) {
                in coins -> 1
                else -> Int.MAX_VALUE
            }
        }

        for (i in coins.indices) {
            for (j in 1 .. k) {
                if (j - coins[i] >= 0) {
                    val prev = if (dp[j - coins[i]] == Int.MAX_VALUE) Int.MAX_VALUE else dp[j - coins[i]] + 1
                    dp[j] = min(dp[j], prev)
                }
            }
        }

        return when (dp[k]) {
            Int.MAX_VALUE -> -1
            else -> dp[k]
        }
    }
}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (n, k) = br.readLine().split(" ").map(String::toInt)
    val coins = IntArray(n) { br.readLine().toInt() }

    bw.append("${Solution2294().solution(k, coins)}\n")
    bw.flush()

    br.close()
    bw.close()
}