마인크래프트(백준)

package com.example.algorithm

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



fun main(){

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

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

    val input = br.readLine().split(' ').map { it.toInt() }

    val n = input[0] //세로
    val m = input[1] //가로
    val b = input[2] //블럭 개수

    var minHeight = 256
    var maxHeight = 0


    repeat(n){//필드 입력
        i ->
        field.add(br.readLine()!!.split(' ').map { it.toInt() }.toMutableList())
        repeat(m){
            j ->
            if(field[i][j]>maxHeight)
                maxHeight = field[i][j]
            if(field[i][j]<minHeight)
                minHeight = field[i][j]
        }
    }

    val answers: MutableList<Pair<Int,Int>> = mutableListOf()
    for(height in minHeight..maxHeight){
        val result = craft(field, height, b)
        if(result!=-1){
            answers.add(Pair(result,height))
        }
    }

    val minValue = answers.minOf { it.first } // 가장 작은 key 값
    val maxValue = answers.filter { it.first == minValue }.maxByOrNull { it.second }?.second // 값이 가장 높은 요소

    bw.write("$minValue $maxValue")
    bw.flush()
    bw.close()


}

fun craft(field:MutableList<MutableList<Int>>,originHeight:Int,originB:Int): Int{
    var time = 0
    var b = originB
    repeat(field.size){
            i->
        repeat(field[0].size){
                j->
            val cur = field[i][j]
            if (cur > originHeight) {
                    time += 2*(cur-originHeight) //시간 증가
                    b += (cur-originHeight) //블럭 갯수 증가

            }
            else if (field[i][j] < originHeight) {
                    time += (originHeight-cur) //시간 증가
                    b -= (originHeight-cur) //블럭 갯수 증가
            }

        }
    }

    if (b < 0) {
        return -1
    }

    return time
}

생각보다 알고리즘이 복잡하여 1차로 막혔으나

브루투포스로 무지성 박치기하면 되는 구나를 깨달고 구현하니 

시간 초과에서 2차로 막히는 문제였다.

 

처음에는 높이들의 평균을 구해 해당 높이가 되게 구현했으나 이는 최적의 경우는 아니여서 가장 낮은 높이부터

가장 높은 높이까지 대입해서 전부 구해주었다.

 

그리고 craft 함수의 경우에도 난잡한 반복문을 최대한 줄여주는 작업이 필요했다.

기존의 이중 반복문 내에 while문이 두개 들어가는 패턴이 두 번 존재했다.

이 때문에 시간초과가 나는 것이라 판단하여 최적화 해주었다.