[백준] 18111번 마인크래프트(브루트 포스 / 완전 탐색)[Kotlin - 코틀린]

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

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

18111번: 마인크래프트

문제

문제 접근

이 문제 개인적으로 초보시절 잠깐 건드렸다가 큰 벽을 느끼고 지레 겁먹고 미루고 미루다가 풀게 되었습니다... 문제를 혼자 복잡하게 생각해서 어렵게 접근을 했었습니다. 막상 브루트 포스로 구현하는 부분은 어렵지 않았습니다... 하지만 시간초과가 발생하여 애를 좀 먹었네요 ...ㅎㅎ

생각의 과정

처음에는 블럭 높이들을 확인하여 그 중에서 최소 높이를 구하는 로직을 짜려고 했었습니다. 평균 및 최솟값등을 이용해서요. 하지만 저의 머리로는 쉽게 떠오르지 않더라구요... 티어만 보고 문제를 판단하고 그러면 안되지만 실버 2라기엔 너무 높은 수준을 요구하는 것 같았습니다...

유형이 브루트 포스이기도 하고 실버 2 문제라서 땅의 높이가 될 수 있는 0 ~ 256까지의 모든 범위를 순차적으로 탐색하게 하였습니다. 예를 들면 0이면 모든 땅의 높이를 0으로 할 때 걸리는 시간(블록 수 고려), 123이라면 모든 땅의 높이를 123으로 할 때 걸리는 시간... 하지만 역시 너무 많은 경우의 수가 발생하여 시간초과 오류가 발생하였습니다. 

조금 생각을 해보니 주어진 땅의 높이의 최솟값, 최댓값의 범위를 넘어갈 일이 없다는 것을 깨달아서 범위를 제한해주었습니다.

 로직은 현재 주어진 땅의 높이의 최댓값 ~ 최솟값를 전부 탐색하여 시간이 가장 적은 경우를 정답 리스트에 넣어 출력하도록 하였습니다.

정답 코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(){

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val ground = mutableListOf<MutableList<Int>>()

    val input = br.readLine().split(" ").map { it.toInt() }
    val col = input[0] // 세로
    val row = input[1] // 가로
    var inven = input[2] // 인벤토리에 있는 블럭의 수
    var timeAndHeight = IntArray(2, {999999999})

    repeat(col){
        val Info = br.readLine().split(" ").map { it.toInt() }.toMutableList()
        ground.add(Info)
    }

    var max = 0
    var min = 999999999
    ground.forEach { col ->
        col.forEach {
            if (it < min) min = it
            if (it > max) max = it
        }
    }
    for (std in min .. max){
        val digAndPut = digAndPut(ground,std,inven)
        if (digAndPut <= timeAndHeight[0]){
            timeAndHeight[0] = digAndPut
            timeAndHeight[1] = std
        }

    }
    bw.write("${timeAndHeight[0]} ${timeAndHeight[1]}")
    bw.flush()
    bw.close()

}
fun digAndPut(ground : MutableList<MutableList<Int>>, std : Int, inven : Int) : Int{
    var time = 0
    // 쓸 수 있는 블록 == 인벤토리에 있는 블록
    var blockCanuse = inven
    for (col in 0 until ground.size){

        for (row in 0 until ground[col].size){
            var cur = ground[col][row]
            if (cur < std){
                time += (std - cur)
                blockCanuse -= (std - cur)
            }
            else if (cur > std){
                time += 2 * (cur - std)
                blockCanuse += (cur - std)
            }
        }
    }
    // 사용한 블록이 쓸 수 있는 블록(캐서 얻은 블록 포함)보다 크다면 불가능 하다는 뜻.
    if (blockCanuse < 0) return 999999999
    return time
}