[백준] 11047번 동전 0(그리디)[Kotlin - 코틀린]

백준 11047번 문제입니다. (solved.ac)기준 실버 3 문제입니다.

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

11047번: 동전 0

문제

문제 접근

그리디 유형을 설명할 때 가장 먼저 나오는 동전 나누기 문제입니다.

1번 입출력 예시 기준 1, 5, 10 ... 10000, 50000 원의 동전들이 있고 이 동전들을 최소한으로 사용하여 4200원을 만들어야합니다.

예를 들어 1원짜리 4200개로도 4200원을 만들 수 있지만 최소한의 동전 갯수를 사용하기 위해선 1000원짜리 4개, 100원짜리 2개를 사용하여 총 6개의 동전으로 4200원을 만들 수 있습니다. 

즉, 4200원을 만들 수 있는 동전들 중 비싼 동전부터 사용해야합니다. 그러기 위하여 가지고 있는 동전들을 내림차순으로 정렬한 후 비싼 동전부터 사용하여 4200원을 만들 수 있는 경우를 탐색하였습니다.

정답 코드

fun main() {

    var (n, k) = readln().split(" ").map { it.toInt() }

    val coinList = mutableListOf<Int>()
    var ans = 0
    
    repeat(n) {
        coinList.add(readln().toInt())
    }

    // 내림차순 정렬
    coinList.sortedByDescending { it }.forEach {
        // 코인이 나누어 진다면 해당 코인만큼 계산해줌.
        val coinCnt = k / it
        if (coinCnt > 0) {
            ans += coinCnt
            k -= coinCnt * it
        }
    }
    
    println(ans)
}