2294번: 동전2 - Kotlin

2294번: 동전 2

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

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

출력

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

 

 

나의 풀이

동전 1에서 파생된 문제이다. 동전 1에서는 경우의 수를 구했는데, 여기서는 개수의 최소값을 구하면 된다. 그 방법으로는 첫번째 동전으로 k까지 가능한 개수를 다 구하고 두번째 동전으로 k까지의 동전의 개수를 구하는데 만약 이전의 방법이 더 좋다면 그 방법으로 진행하게하는 방식으로 진행하였다.

 

 

import kotlin.math.*

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }

    val coin = Array(n) { readLine().toInt() }

    val dp = IntArray(k + 1) { Int.MAX_VALUE }

    dp[0] = 0

    for(i in 0 until n){
        for(j in coin[i]..k){
            if (dp[j - coin[i]] != Int.MAX_VALUE)
                dp[j] = min(dp[j], dp[j - coin[i]] + 1)
        }
    }

   if (dp[k] == Int.MAX_VALUE)
       println(-1)
   else
       println(dp[k])
}