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

출처: unsplash.com

 

마인크래프트(18111번)

Silver 2

#구현 #브루트포스 알고리즘

 

문제 내용

 

 

문제 접근

문제에서 주어진 높이는 0부터 256까지이다.

이 높이를 이용해 반복문을 돌려서 높이가 g 일 때 높이가 g인 평평한 바닥을 만들기 위해 얼마나 시간이 걸리는지 확인해야 한다.

그전에 입력된 값에서 어떤 높이의 블록이 몇 개 들어 있는지 확인해야 한다.

그 값은 Map으로 저장할 것이다. key를 높이, value를 개수로 정하겠다.

val block = mutableMapOf<Int, Int>()

이제 위에서 언급했다시피 0 ~ 256까지 반복해서 돌아 준다.

돌면서 기존의 입력값에서 높이가 g인 평지를 만들기 위해 블록을 얼마나 캐고 설치해야 하는지 계산해야 한다.

블록을 캐는 작업은 2초가, 블록을 설치하는 데는 1초의 시간이 소요된다.

현재 g보다 map의 블록의 높이(key)가 더 작으면 블록을 설치해 주는 작업이 필요하다.

 

<조건 1>

b.key < g 인 경우, 

설치해야 하는 블록의 개수를 Kotlin 코드로 나타내 보면 다음과 같다.

(g(현재 높이) - b.key(블록의 높이)) * b.value(블록의 개수)

위 식을 적용하면 높이가 b.key인 블록들을 높이 g로 만들기 위해 채워야 하는 블록의 수를 구할 수 있다.

인벤토리에는 채워야 하는 블록만큼 빼준다.

inventory -= fillCnt

설치하는 데 걸리는 시간은 1초이므로 시간은 fillCnt만큼 걸린다.

time += fillCnt

 

<조건 2>

b.key > g 인 경우,

제거해야 하는 블록의 개수를 코드로 나타내면 다음과 같다.

(b.key - g) * b.value

위 식으로 제거해야 하는 블록의 수를 구하고, 인벤토리에 추가해 준다.

inventory += removeCnt

블록을 제거하는 데 2초가 걸리기 때문에 removeCnt * 2만큼의 시간이 소요된다.

time += (removeCnt * 2)

 

<조건 3>

조건 1, 2를 모두 확인하고 inventory가 0보다 작으면 인벤토리가 부족하다는 뜻이라 g만큼의 높이를 가진 평지를 만드는 것이 불가능하기 때문에 continue.

if (inventory < 0) continue

현재 최소 시간과 새로 구한 시간과 현재 시간의 최솟값을 각각 구해 주고, 두 개의 값이 서로 다르면 더 적은 값으로 변경되었다는 뜻이 된다.

val currentMin = res[0]
val changeMin = min(res[0], time)

 

 

<조건 4>

현재 시간과 새로 구한 최솟값이 서로 다르다면, 새로운 최솟값이 정해졌다는 뜻이다. 이것을 코드로 나타내 보면 다음과 같다.

currentMin != changeMin

이 조건을 만족하면 변경된 최솟값과 최솟값을 만드는 데 설정한 높이를 새로 적용한다.

 

<조건 5>

만약 걸린 시간이 같은 경우도 있다. 현재 시간과 새로 구한 최솟값이 같다면, g만 갱신해 주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main() = with (BufferedReader(InputStreamReader(System.`in`))) {
    val (n, m, inv) = readLine().split(" ").map { it.toInt() }
    val block = mutableMapOf<Int, Int>()

    for (i in 0 until n) {
        val blocks = readLine().split(" ").map { it.toInt() }

        for (j in blocks.indices) {
            if (!block.containsKey(blocks[j])) block[blocks[j]] = 1
            else block[blocks[j]] = block[blocks[j]]!! + 1
        }
    }

    var res = listOf(Int.MAX_VALUE, -1)
    for (g in 0 .. 256) {
        // g: 현재 땅의 높이
        var time = 0
        var inventory = inv

        for (b in block) {
            if (b.key < g) {
                // 현재 땅보다 block의 높이가 낮으면 인벤토리에서 블록을 꺼내서 채워주어야 함.
                val fillCnt = (g - b.key) * b.value
                inventory -= fillCnt
                time += fillCnt
            } else if (b.key > g) {
                // 현재 땅보다 block의 높이가 높으면 현재 땅 높이까지 블록을 제거해 인벤토리에 넣어주어야 함.
                val removeCnt = (b.key - g) * b.value
                inventory += removeCnt
                time += (removeCnt * 2)
            }
        }

        if (inventory < 0) continue
        else {
            // 현재 최솟값과 변경된 최솟값이 변경되었는지 확인해야함.
            val currentMin = res[0]
            val changeMin = min(res[0], time)

            // 값이 변경되었으면 더 적은 시간이 들었다는 뜻이므로 ground 도 변경.
            if (currentMin != changeMin) res = listOf(changeMin, g)
            // 걸린 시간이 같으면 가장 높은 값을 구해 주어야 함.
            else if (currentMin == time) res = listOf(currentMin, g)
        }
    }

    println(res.joinToString(" "))
}

 

문제 풀이

입력값을 모두 map에 저장해 준다. key에는 block의 높이가, value에는 block의 개수가 들어간다.

0부터 256까지 반복하면서 map에서 조건 1과 조건 2를 적용해 남은 인벤토리와 걸린 시간을 구해 준다.

for (b in block) {
    if (b.key < g) {
        // 현재 땅보다 block의 높이가 낮으면 인벤토리에서 블록을 꺼내서 채워주어야 함.
        val fillCnt = (g - b.key) * b.value
        inventory -= fillCnt
        time += fillCnt
    } else if (b.key > g) {
        // 현재 땅보다 block의 높이가 높으면 현재 땅 높이까지 블록을 제거해 인벤토리에 넣어주어야 함.
        val removeCnt = (b.key - g) * b.value
        inventory += removeCnt
        time += (removeCnt * 2)
    }
}

걸린 시간과 남은 인벤토리를 구했다.

그러면 조건 3을 통해 평지 g를 만드는 게 불가능하면 continue로 건너뛴다.

 

그리고 조건 4, 조건 5를 체크해서 결괏값을 변경해 준다.

 

 

문제 해결 과정

높이를 0부터 256으로 가정하고 반복하면서 최소 시간과 최소 시간에 해당하는 높이를 구해주면 되는 문제였다.

문제 질문 게시판에서는 완전 탐색을 이용했다는 게시물이 종종 보여서 이렇게 쉬운 풀이법을 찾아내지 못했다.

제한 시간이 추가 시간이 없는 1초라서 입력값을 그대로 끌고 와서 사용하면 시간 초과가 날 수도 있다.

Map을 이용해 해당 높이에 블록이 몇 개 있는지 확인해 주어야 더 빠르게 값을 구할 수 있다.