BOJ 18111_마인크래프트

문제

풀이

package solve_18111

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val n = input()
    val m = input()
    val b = input()

    var heightSum = 0
    var minHeight = Int.MAX_VALUE
    var maxHeight = Int.MIN_VALUE
    var answer = Answer(Int.MAX_VALUE,Int.MIN_VALUE)

    val map = Array(n) {
        IntArray(m) {
            val height = input()
            heightSum += height
            minHeight = minOf(height, minHeight)
            maxHeight = maxOf(height, maxHeight)
            height
        }
    }
    for (target in minHeight..maxHeight) {
        var time = 0
        var nowInventory = b
        var flag = false
        for (i in map.indices) {
            for (j in map[0].indices) {
                if (map[i][j] > target) {
                    time += (map[i][j] - target) * 2
                    nowInventory += map[i][j] - target
                }
            }
        }
        for (i in map.indices) {
            for (j in map[0].indices) {
                if (map[i][j] < target) {
                    if (target - map[i][j] <= nowInventory) {
                        time += target - map[i][j]
                        nowInventory -= target - map[i][j]
                    } else {
                        flag = true
                        break
                    }
                }
            }
            if(flag) break
        }
        if(flag.not()){
            answer = minOf(answer, Answer(time, target))
        }
    }
    println("${answer.time} ${answer.height}")

}

private data class Answer(val time: Int, val height: Int) : Comparable<Answer>{
    override fun compareTo(other: Answer) = compareValuesBy(this, other, {it.time}, {-it.height})

}

사용 알고리즘

부르드포스 완전탐색

우선 입력받으면서 최대, 최소를 저장해 두었다.

이후 최소부터 하나씩 target으로 지정 후 해당 비용을 계산하였다.
먼저 전체 맵을 돌면서 목표보다 높은 블럭의 경우 블럭을 깎아내고 그만큼 인벤토리에 넣고 시간 비용을 추가해 주었다.
이후 다시 맵을 탐색하며 target값 만큼 블럭을 채워 주었다.
이 과정에서 인벤토리의 갯수가 부족할 경우 효율을 높이기 위해 flag를 통해 반복문을 탈출해 주었다.

이후 문제의 조건에 맞게 answer의 값을 비교하여 가장 짧은 시간에 높은 층의 값을 가지는 것을 출력해 주었다.