[백준] #18111: 마인크래프트

1. Problem Link

• https://www.acmicpc.net/problem/18111

2. Notation

• n : length of height
• m : length of width
• b : initial number of block
• land : 2-dimension array (n x m)
• low : min value of land
• high : max value of land

3. Source Code

• It is obvious that height which is the answer of this problem would be between low and high calculated advanced.
• So, we don't need to iterate 0 to 256 which means we can reduce time complexity slightly.

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (n, m, b) = br.readLine().split(" ").map { it.toInt() }
    val land = Array(n) { mutableListOf<Int>() }
    var low = Int.MAX_VALUE
    var high = 0
    repeat(n) { i ->
        val heights = br.readLine().split(" ").map { it.toInt() }
        for (height in heights) {
            low = minOf(low, height)
            high = maxOf(high, height)
        }
        land[i].addAll(heights)
    }

    var time = Int.MAX_VALUE
    var answer = 0
    for (height in low..high) {
        var _b = b
        var _time = 0
        for (i in 0 until n) {
            for (j in 0 until m) {
                val diff = land[i][j] - height
                if (diff < 0) {
                    _b -= -diff
                    _time += -diff
                } else if (diff > 0) {
                    _b += diff
                    _time += 2 * diff
                }
            }
        }
        
        if (_b < 0) continue
        if (_time <= time) {
            time = _time
            answer = maxOf(answer, height)
        }
    }
    bw.write("$time $answer")

    br.close()
    bw.close()
}

4. Complexity

• Time : O(n x m)
• Space : O(n x m)