백준 2294 [kotlin]

문제

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

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

입력

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

출력

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

코드

import java.lang.Integer.min

fun main()
{
    var coinArr : IntArray = IntArray(10001,{10001})
    coinArr[0] = 0
    var input = readLine()!!.split(" ").map {it.toInt()}
    var n = input[0]
    var k = input[1]

    var coinPrice : IntArray = IntArray(101,{0})

    repeat(n)
    {
        i ->
        coinPrice[i] = readLine()!!.toInt()
        for (j in coinPrice[i]..k)
        {
            coinArr[j] = min(coinArr[j], coinArr[j - coinPrice[i]] + 1)
        }
    }

    if(coinArr[k] == 10001) println(-1)
    else println(coinArr[k])

}