백준 19942번 코틀린 + 반례 2개

무난한 백트래킹 문제인데 나온지 얼마 안 된 문제이다보니 인터넷에 코틀린 코드가 하나도 없더군요...

 

data class food(val p: Int, val f: Int, val s: Int, val v: Int, val price: Int)

fun main() {
    // 인풋
    val n = readLine()!!.toInt()
    val temp = readLine()!!.split(" ").map { it.toInt() }
    val mp = temp[0]
    val mf = temp[1]
    val ms = temp[2]
    val mv = temp[3]

    val foods = ArrayList<food>(n)

    repeat(n) {
        val temp = readLine()!!.split(" ").map { it.toInt() }
        foods.add(food(temp[0], temp[1], temp[2], temp[3], temp[4]))
    }

    
    // 구현
    val answer = StringBuilder()
    val trace = ArrayList<Int>()
    val visited = BooleanArray(n)
    var minPriceSum = Int.MAX_VALUE

    fun dfs(index: Int, pSum: Int, fSum: Int, sSum: Int, vSum: Int, priceSum: Int) {
        val newPSum         = pSum + foods[index].p
        val newFSum         = fSum + foods[index].f
        val newSSum         = sSum + foods[index].s
        val newVSum         = vSum + foods[index].v
        val newPriceSum     = priceSum + foods[index].price

        visited[index] = true
        trace.add(index)

        if (newPriceSum >= minPriceSum) { // 더 이상 탐색할 가치 없음 -> return -> 시간 절약
            return
        }

        if (newPSum >= mp && newFSum >= mf && newSSum >= ms && newVSum >= mv) { // 영양 충분
            answer.clear()
            minPriceSum = newPriceSum
            answer.append("$newPriceSum\n")
            trace.forEach { answer.append("${it + 1} ") }

            return
        } else { // 영양 불충분 -> 다른 식재료 추가

            for (i in index + 1 until foods.size) {
                if (!visited[i]) {
                    dfs(i, newPSum, newFSum, newSSum, newVSum, newPriceSum)
                    trace.removeLast()
                    visited[i] = false
                }
            }

        }
    }

    
    // 백트래킹 dfs
    for (i in foods.indices) {
        trace.clear()
        visited.fill(false)

        dfs(i, 0, 0, 0, 0, 0)
    }

    
    // 출력 (정답 없을 시 -1 출력)
    println(answer.ifBlank { -1 })
}

 

 

괜히 속도 높여보겠다고 처음에 foods 중 가성비 좋은 애들 기준으로 정렬해서 풀었었는데 그 경우 다음 반례에 막힙니다.

4
10 10 10 10
8 8 8 8 3
2 2 2 2 2
6 6 6 6 1
4 4 4 4 4

정답은

4

1, 2

입니다.

 

그런데 이걸 foods에서 가성비 좋은 애부터 탐색하다보면 정답이 3, 4라고 하는데 두 경우다 가격이 5원이라서 정답 후보가 맞지만 문제에서 '같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.'라고 하였기 때문에 3, 4보다 1, 2가 사전 순으로 빨라서 1, 2를 출력해야 합니다.

 

따라서 괜히 foods를 가성비 순으로 재정렬하는 짓은 하지 말고 그냥 인풋 들어오는 대로 써야합니다.

 

 

제가 고생한 또 다른 반례가 있는데

1
1 1 1 1
0 0 0 0 0

 

정답은 -1입니다.

 

출력 조건에 '조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.'라고 적혀있습니다.

보통은 이런 조건이 있으면 예제에도 -1이 출력되는 경우를 추가해놓기 마련인데 여긴 예제에 그런 게 없어서 출력 조건에 딱 1줄 적혀있는 저 문장을 안 보고 지나친다면 틀렸습니다.의 늪에 빠지게 되죠...