[백준] 11047번 동전0

백준 11047번 - 동전0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

접근 방법

가장 비싼 돈 부터 확인하면서, 해당 금액으로 낼 수 있는 최대한의 금액을 내면 동전을 최소한으로 사용할 수 있다.

코드

class IO11047 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getNK() = br.readLine().split(" ").map { it.toInt() }
    fun getValue() = br.readLine().toInt()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    var answer = 0
    var curMoney = 0
    val io = IO11047()

    val (N, K) = io.getNK()

    val coins = Array(N) { 0 }

    repeat(N) {
        coins[it] = io.getValue()
    }

    coins.sort()

    for (idx in coins.lastIndex downTo 0) {
        val div = coins[idx]
        val now = K - curMoney
        val q = now / div
        val r = now % div
        if (q > 0) {
            curMoney += div * q
            answer += q
        } else {
            continue
        }
    }
    io.write(answer.toString())
    io.close()
}