[백준] 18111 (마인크래프트)

#1 알고리즘

#1-1 입력 읽기

N개의 행과 M개의 열을 가진 2차원 배열 blockHeights를 선언한다. blockHeights 각 원소의 값에는 해당 위치의 높이를 할당한다.

 

#1-1 문제풀이 개요

땅이 고른 상태의 블록 갯수는 0, (N*M), (N*M)*1, (N*M)*2, (N*M)*3, ..., (N*M)*256 중 하나다. 이 중에서, (현재 놓여진 블록의 갯수) + (인벤토리 속 블록의 갯수)보다 작거나 같은 갯수들 중 최대값인 갯수를 구한다.

그 갯수를 (N*M)로 나누면, 땅을 고르게 만들 수 있는 최대 높이가 된다. 0부터 해당 높이까지의 정수 범위를 내림차순으로 순회(인덱스 i)한다. 내림차 순인 이유는 문제의 조건에서, 같은 소요 시간일때는 더 큰 높이를 정답으로 제출하라고 했기 때문이다. 순회 중 calculateWorkTime(i)를 기록하며 더 작은 값이 나올 때마다 갱신한다. 순회 종료 후 해당 값을 출력한다.

 

#1-2 fun cacluateWorkTime(targetHeight: Int): Int

blockHeights를 순회하며 각 원소의 높이를 targetHeight로 만드는데 필요한 시간들을 모두 더해 반환한다. 

 

#2 코드 - 코틀린

import kotlin.math.abs

fun main() {
    val firstInformations = readln().split(" ")
    val N = firstInformations[0].toInt() // 행의 갯수
    val M = firstInformations[1].toInt() // 열의 갯수
    val B = firstInformations[2].toInt()

    val blockHeights: Array<Array<Int>> = Array(N) {Array(M) {0} }
    var blockCount = 0
    for(n: Int in 0..<N) {
        val blockHeightsOfLine = readln().split(" ")

        for(m: Int in 0..<M) {
            val blockHeight = blockHeightsOfLine[m].toInt()
            blockHeights[n][m] = blockHeight
            blockCount += blockHeight
        }
    }

    /* 땅이 고른 상태의 블록 갯수는 0, (N*M), (N*M)*1, (N*M)*2, (N*M)*3, ..., (N*M)*256 중 하나다.
     * 이 중에서,
     * blockCount(현재 놓여진 블록의 갯수) + B(인벤토리 속 블록의 갯수)보다
     * 작거나 같은 갯수 중 최대값인 갯수를 구한다. (targetBlockCount)
     */
    var maxBlockCount = 0
    while(maxBlockCount + (N*M) <= blockCount + B) {
        maxBlockCount += (N*M)
    }
    val maxHeight = maxBlockCount / (N*M)

    // maxHeight일 때, 최소 작업 시간(minTime) 구하기
    var minTime = calculateWorkTime(blockHeights, maxHeight)
    var heightAtMinTime = maxHeight
    
    // 1..<maxHeight일 때, 최소 작업 시간(minTime) 구하기
    for(height: Int in (maxHeight - 1) downTo 0) {
        val tempTime = calculateWorkTime(blockHeights, height)
        if(tempTime < minTime) {
            minTime = tempTime
            heightAtMinTime = height
        }
    }
    
    println("$minTime $heightAtMinTime")
}

fun calculateWorkTime(blockHeights: Array<Array<Int>>, targetHeight: Int): Int {
    var workTime = 0

    for(row in blockHeights) {
        for(height in row) {
            workTime += if(0 < targetHeight - height) {
                targetHeight - height
            } else {
                abs(targetHeight - height) * 2
            }
        }
    }

    return workTime
}