[백준] 11047 동전 0 (코틀린 kotlin)

 

문제 링크

 

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

11047번: 동전 0

 

 

 

문제 풀이

 

fun main() = with(System.`in`.bufferedReader()) {
    var (n, k) = readLine().split(" ").map { it.toInt() }
    val coins = mutableListOf<Int>()
    var result = 0
    repeat(n) {
        coins.add(readLine().toInt())
    }
    coins.sortedByDescending{ it }.forEach {
        val cnt = k / it
        if (cnt > 0) {
            result += cnt
            k -= cnt * it
        }
    }
    println(result)
}

 

 

단순한 그리디 알고리즘 문제입니다.

동전 개수를 최소화하기 위해서는 값이 큰 동전부터 사용해야 합니다.

이에 따라, 받아온 동전들을 내림차순 정렬해준 후

값이 큰 동전부터 남은 금액에 대해 사용할 수 있는 개수만큼 사용하여 금액을 줄여나가면 되는 문제입니다.