[6개월 안에 백준 플래티넘 달성하기] 4. 마인크래프트_18111 | 코틀린

2023. 10. 7 ~ 2023. 10. 24  백준 솔브 CLASS2 문제 풀이 완료,  실버 3

 

Class 2까지 모든 문제를 클리어했습니다. 실버 2 문제부터 바로바로 풀이가 되지 않고 조금씩 막히면서 난이도가 올라갔음을 느끼고 있습니다. 그런 의미에서 Class 2의 마지막 문제  마인크래프트_18111를 가져왔습니다.

 

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

 

정리하자면,

N x M의 땅에 높이가 부여되어 있고 땅 블록을 가진 인벤토리(B)가 제공될 때 모든 땅의 높이를 최단 시간 안에 동일하게 만들어주면 된다.

이때 땅의 높이를 바꾸는 방법은

1. 땅 1을 제거하고 인벤토리에 넣는다. (1초 소요)
2. 땅 1을 인벤토리에서 꺼내어 블록 위에 놓는다. (2초 소요)

 

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

 

예제

예제 입력	예제 출력
3 4 99 0 0 0 0 0 0 0 0 0 0 0 1	2 0

 

첫 번째 풀이

문제를 처음 봤을 때 딱히 풀이 방법이 생각나지 않았습니다. 이럴 때 저는 가장 먼저 브루트포스 알고리즘으로 풀 수 있는지 확인합니다

 

해당 문제의 경우 최대 땅의 크기 500 x 500에 땅의 최대 높이가 256이다. 따라서 모든 경우의 수를 따져도 500 x 500 x 256 이므로 그렇게 많은 시간이 소요되지 않습니다.

 

결과적으로 0부터 256의 모든 높이에 대해 평탄화작업을 하였을 때 가장 적은 시간을 소요한 경우를 구하면 됩니다.

 

fun main() = with(System.`in`.bufferedReader()) {
    val (N, M, B) = readLine().split(" ").map { it.toInt() }
    val arr = List(N) { readLine().split(" ").map {it.toInt()}.toMutableList() }

    var minTime = Int.MAX_VALUE
    var high = 0
    
    // 0부터 256 높이까지 모든 범위
    for (h in 0..256) {
        var b = B
        var time = 0
        
        // N x M
        for (i in 0 until N) {
            for (j in 0 until M) {
            	// 평탄화 높이보다 땅의 높이가 크면 땅 블록을 제거해준다. (2초 소요)
                if (h < arr[i][j]) {
                    b += (arr[i][j] - h)         // 제거한 블록 인벤토리에 추가
                    time += (arr[i][j] - h) * 2  // 제거한 시간
                } else {
                // 평탄화 높이보다 땅의 높이가 작거나 같으면 땅 블록을 추가해준다. (1초 소요)
                    b -= (h - arr[i][j])      // 부족한 땅 블록을 인벤토리에서 가져온다
                    time += (h - arr[i][j])   // 제거한 시간
                }
            }
        }
        
        // 인벤토리에 땅 블록이 음수인 경우 -> 평탄화가 불가능
        if (b < 0) continue

		// 최단 시간을 구해준다. (최단 시간이 같을 경우 최고 높이)
        if (minTime > time) {
            minTime = time
            high = h
        } else if (minTime == time && high < h) {
            high = h
        }
    }
    print("$minTime $high")
}

 

여기서 코드를 조금만 수정해도 시간 초과가 날 수 있습니다. 이 부분이 백준에서 문제를 풀 때 아쉬운 점인데

가장 먼저 입출력을 신경 써줘야 합니다. 그냥 readln()을 쓸 경우 시간 초과가 뜹니다.

두 번째로 else 대시 else if를 쓰면 마찬가지로 시간 초과가 뜹니다.

세 번째로 주석 때문에 시간 초과가 뜨는 경우가 있었습니다.

 

이런 요소들 때문에 풀이 시간이 길어졌던 거 같습니다.

 

두 번째 방법

다른 분의 풀이 방법으로 좀 더 개선된 방법입니다.

모든 경우의 수를 구하는 것이 아닌, 주어진 땅 블록의 높이에서 최소 높이와 최대 높이를 구한 뒤 그 안에서 최소의 시간으로 평탄화하는 방법을 찾으면 됩니다.

 

이를 위해 각 높이를 인덱스로 가지는 257 크기의 배열을 생성한 뒤 각 높이별 개수를 배열에 담아주면 됩니다.

위의 예제가 입력값으로 들어올 경우 배열은 [11, 1, 0, 0, 0..., 0]이 되며 이를 [12, 0, 0, 0, 0,..., 0]으로 만들어 주는 과정에서 답을 구할 수 있습니다.

fun 마인크래프트_개선된풀이() = java.io.StreamTokenizer(System.`in`.bufferedReader()).run {
    fun i(): Int {
        nextToken(); return nval.toInt()
    }

    val n = i() * i() // 땅의 총 개수
    var b = i()       // 인벤토리
    var time = 0    
    var min = 256
    var max = 0
    val blocks = IntArray(257) // 각 높이별 땅 블록의 개수를 담는 배열

    // 각 땅의 블록 개수를 체크해준다.
    repeat(n) {
        val blockHeight = i()
        min = minOf(blockHeight, min)
        max = maxOf(blockHeight, max)
        blocks[blockHeight]++ 
    }
    
    // 예제의 경우 blocks = [11, 1, 0, 0, 0, 0 ... 0]

    // blocks을 [n,0,0,0,0, ... 0] 형태로 완성시키면 됨
    // 땅 블록 이동 작업
    while (min < max) {
        // 인벤토리로 커버가능하고 && 땅을 파는것 보다 땅을 추가하는게 시간이 더 적게 걸릴 경우
         if (b >= blocks[min] && blocks[min] <= blocks[max] * 2) {
         	// 땅을 추가한다. (1초)
            val currentBlockCount = blocks[min]  // 높이가 min인 블록의 개수
            time += currentBlockCount
            b -= currentBlockCount
            blocks[min + 1] += currentBlockCount // 땅을 추가했기에 높이가 min+1인 블록이 됨
            blocks[min] = 0                      // 기존의 높이가 min인 블록의 개수는 0이 됨
            min++
        } else {  
        // 인벤토리에 땅이 없거나, 땅을 파는게 시간이 더 적게 걸리는 경우
        	// 땅을 판다. (2초)
            val currentBlockCount = blocks[max]
            time += currentBlockCount * 2
            b += currentBlockCount
            blocks[max - 1] += currentBlockCount
            blocks[max] = 0
            max--
        }
    }

    print("$time $max")
}

 

 

 

최소 높이가 0이고 최대 높이가 256인 최악의 경우에서도 복잡도는 256이 됩니다.

 

딱히 어려운 알고리즘 기법이 들어가지 않은 간단한 풀이 방법이지만, 처음 이 풀이를 접하고 이해하는 데까지 생각보다 많은 시간이 걸렸습니다.

더 많은 문제를 접하면서 감을 익혀야 될 거 같습니다.