[백준 18111] [Kotlin] 마인크래프트

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

18111번: 마인크래프트

 

 

난이도 : 실버 2
태그 : 브루트포스, 구현

 

---

 

설명

 

고르지 못한 땅을 평탄화 하는 문제입니다.

 

처음에는 높은 블록을 떼서 아래쪽에 넣는 방법을 생각해 봤으나...

한참의 삽질 끝에 마침내 브루트포스 문제인걸 깨달았습니다.

 

블록의 최소 높이부터 최대 높이까지 모든 경우의 수를 확인하여

평탄화가 된 케이스를 찾으면 됩니다.

 

 

 

---

코드

val br = BufferedReader(InputStreamReader(System.`in`))

val nmb = br.readLine().split(" ")
val n = nmb[0].toInt()
val m = nmb[1].toInt()
val initialInventory = nmb[2].toInt()

val map = Array(n) { Array(m) { 0 } }

repeat(n) { x ->
    val st = StringTokenizer(br.readLine()," ")
    for(y in 0 until m) {
        map[x][y] = st.nextToken().toInt()
    }
}

버퍼리더를 이용해 인풋을 받았고,

StringTokenizer를 이용하여 각 map에 할당하였습니다.

 

 

var minH = 257 // 최대 땅의 높이는 256
var maxH = 0

for (i in 0 until n) {
    for (j in 0 until m) {
        val height = map[i][j]
        maxH = max(maxH, height)
        minH = min(minH, height)
    }
}

최대 높이값과 최소 높이값을 찾는 부분입니다.

블록의 범위는 0 ~ 256 이므로 최대값을 257로 잡았습니다.

 

 

// 파는데 2초, 놓는데 1초
var minSpentTime = Int.MAX_VALUE
var resultH = 0

for(h in minH .. maxH) {
    var inventory = initialInventory
    var spentTime = 0

    for(x in 0 until n) {
        for(y in 0 until m) {
            if(map[x][y] < h) {
                // 놓는 작업
                val d = h - map[x][y]
                spentTime += d
                inventory -= d
            } else if(map[x][y] > h) {
                // 파는 작업
                val d = map[x][y] - h
                spentTime += d * 2
                inventory += d
            }
        }
    }

    if(inventory >= 0 && spentTime <= minSpentTime) {
        minSpentTime = spentTime
        resultH = h
    }
}

 

map의 최소 높이부터, 최대 높이까지 반복문을 돌립니다.

 

map[x][y]는 해당 좌표의 블록의 높이값이 저장되 있으며,

현재 확인하려는 높이 h 보다 높다면 블록을 제거하는 작업을,

현재 확인하려는 높이 h 보다 낮다면 블록을 놓는 작업을 진행하게 됩니다.

 

파는 작업에는 2초, 놓는데는 1초가 걸리니 spentTime 에 작업시간을 더해주고,

inventory에도 팠을 경우엔 +를, 놓았을 경우에는 -연산을 진행합니다.

 

최종적으로, inventory의 값이 -면 해당 높이 h로 평탄화하는 것은 불가능 하다는걸 의미합니다.

 

따라서, inventory의 값이 0 이상이거나, 현재 소모된 시간이 이전까지의 minSpentTime보다 작다면

minSpentTime에 현재 spentTime을 할당하고, 출력할 resultH에도 현재의 높이값을 저장합니다.

 

println("$minSpentTime $resultH")

 

마지막으로 결과값을 출력합니다.

 

 

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.max
import kotlin.math.min

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val nmb = br.readLine().split(" ")
    val n = nmb[0].toInt()
    val m = nmb[1].toInt()
    val initialInventory = nmb[2].toInt()

    val map = Array(n) { Array(m) { 0 } }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine()," ")
        for(y in 0 until m) {
            map[x][y] = st.nextToken().toInt()
        }
    }

    var minH = 257 // 최대 땅의 높이는 256
    var maxH = 0

    for (i in 0 until n) {
        for (j in 0 until m) {
            val height = map[i][j]
            maxH = max(maxH, height)
            minH = min(minH, height)
        }
    }

    // 파는데 2초, 놓는데 1초
    var minSpentTime = Int.MAX_VALUE
    var resultH = 0

    for(h in minH .. maxH) {
        var inventory = initialInventory
        var spentTime = 0

        for(x in 0 until n) {
            for(y in 0 until m) {
                if(map[x][y] < h) {
                    // 놓는 작업
                    val d = h - map[x][y]
                    spentTime += d
                    inventory -= d
                } else if(map[x][y] > h) {
                    // 파는 작업
                    val d = map[x][y] - h
                    spentTime += d * 2
                    inventory += d
                }
            }
        }

        if(inventory >= 0 && spentTime <= minSpentTime) {
            minSpentTime = spentTime
            resultH = h
        }
    }

    println("$minSpentTime $resultH")
}

 

---

 

후기

 

마인크래프트를 소재로 한 꽤 참신한 문제였던 것 같습니다.

 

처음엔 브루트포스 알고리즘을 떠올리지 못해 꽤나 삽질을 한 문제였습니다 ㅎㅎ...

 

처음엔 코틀린의 readLine()과 readLine()!!.split(" ").toTypedArray() 를 이용하여 입력 및 배열할당을 하였는데,

 

시간초과가 나서... bufferedReader와 StringTokenizer를 사용하여 풀었더니 시간초과 없이 잘 풀리더군요.

 

bufferedReader와 StringTokenizer를 쓰는 습관을 들여야 할 것 같습니다.