[Kotlin] 백준 11047 동전 0

📘 문제

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

💡 풀이

접근은 단순하게 그리디로 생각을 했다.

결국 주어진 동전들을 최소로 사용하여 주어진 k를 만드는 것이고, 큰 값의 동전부터 차례대로 사용하면 필요한 동전 개수의 최솟값이 나오기 때문이다.

💻 코드

private fun main() {
    var (n, k) = readln()!!.split(" ").map { it.toInt() }
    // 가치의 합을 k로 만들자
    // 동전 개수의 최솟값 구하기
    // 비싼 동전부터 사용하자
    var answer = 0

    val arr = IntArray(n)
    for (i in 0 until n) {
        arr[i] = readln().toInt()
    }
    
    for (i in n - 1 downTo 0) {
        val coinCount = k / arr[i]
        if (coinCount == 0) continue
        // k값 갱신
        k %= arr[i]
        // 필요한 동전 개수 갱신
        answer += coinCount
    }
    println(answer)
}

결과