[백준 kotlin] 19845 넴모넴모2020

문제

 

격자에 넴모가 배치되어있고 좌표를 설정하여 레이저를 배치했을 때 몇마리의 넴모가 사라지는 지 구하는 문제이다.

---

풀이

먼저 넴모의 배치를 보면 중력을 받기 때문에 한 위치를 잡았을 때 그 위치보다 아래층에 넴모가 무조건 배치되어있다. 
레이저의 영향을 받는 넴모는 본문에서는 어렵게 설명하였는데 결국 레이저의 위치를 기준으로 오른쪽과 위쪽에 넴모들이 영향을 받는다.

 

따라서 문제를 해결하려면 레이저의 위치를 기준으로 해당 위치 + 오른쪽 + 위쪽의 넴모의 개수를 카운트하면된다.

 

val (N, Q) = readLine().split(" ").map { it.toInt() }
val states = readLine().split(" ").map { it.toInt() }
val maxNum = states.maxOrNull()

먼저 필요한 정보를 입력받는다. 

states 는 넴모의 위치를 나타내는 변수로 [3, 3, 2] 일경우 1층 3개 2층 3개 3층 2개의 넴모로 이루어져있다는 걸 의미한다.

 

Q는 레이저의 개수를 의미하므로 Q만큼 반복한다

repeat(Q) {
    var answer = 0
    val(x, y) = readLine().split(" ").map { it.toInt() }
    var start = 0
    var end = N
    answer += states[y - 1] - x

레이저의 x, y좌표를 입력받고, start, end값을 초기화한다. start, end는 각각 레이저의 영향을 받는 넴모의 최소y좌표, 최대 y좌표를 의미한다.

 

레이저의 영향을 받는 레이저 기준 오른쪽 넴모의 경우 states[y - 1] - x 로 구할 수 있다. 이는 레이저와 같은 y좌표에 있는 넴모의 개수이다.

 

문제는 레이저와 같은 x좌표에 있는 넴모의 개수를 구해야 한다. 즉 레이저 기준 위쪽에 있는 넴모의 개수를 구하는 것이 관건이다.

레이저의 위치를 기준으로 해당 위치보다 얼마나 높은 위치까지 넴모가 배치되어있는지 알기 어렵기 때문이다.

 

이 문제를 해결하기 위해 이분탐색을 사용하였다.

이분탐색에서 위치를 잡은 후 해당위치에 넴모가 있냐 없냐에 따라 판단하면 된다.

while (start < end) {
    var mid = (start + end) / 2
    if (states[mid] < x) {
        end = mid
    } else {
        start = mid + 1
    }
}

states[mid]값이 x보다 작다면 즉 해당 층수에 넴모가 레이저위에 없다면 end = mid로 할당한다.

만약 있다면 start = mid + 1로 할당한다.

이렇게 할당하면 최종적으로 start값에 가장 높은 층수가 기록된다.

 

answer += start - y + 1
if (x > maxNum!! || y > N || answer <= 0) {
    println(0)
} else {
    println(answer)
}

 

 

마지막으로 answer값에 start - y + 1 값을 할당하고 print해준다. 

이 때 레이저의 좌표가 넴모가 위치한 좌표보다 위 또는 아래에 배치될 수 있으므로 그 경우를 예외처리해준다.

---

코드

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


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val (N, Q) = readLine().split(" ").map { it.toInt() }
    val states = readLine().split(" ").map { it.toInt() }
    val maxNum = states.maxOrNull()

    repeat(Q) {
        var answer = 0
        val(x, y) = readLine().split(" ").map { it.toInt() }
        var start = 0
        var end = N
        answer += states[y - 1] - x
        while (start < end) {
            var mid = (start + end) / 2
            if (states[mid] < x) {
                end = mid
            } else {
                start = mid + 1
            }
        }
        answer += start - y + 1
        if (x > maxNum!! || y > N || answer <= 0) {
            println(0)
        } else {
            println(answer)
        }
    }
}