[백준/BOJ] 2212번: 센서

문제

https://www.acmicpc.net/problem/2212

2212번: 센서

해설

문제를 요약해 보자면, n개의 센서와 k개의 집중국이 있을 때 집중국의 수신 가능영역의 최소 거리 합을 구하는 것이다.

센서는 평면상의 직선에 있으므로, 각 센서의 거리를 구하기 위해 오름차순으로 센서의 위치를 정렬해 준다.

문제의 예시 1을 보면 센서의 위치는 [1, 3, 6, 6, 7, 9]가 된다.

각 센서의 거리 사이는 [2, 3, 0, 1, 2]이 되는 것을 알 수 있다.

센서 사이의 거리를 정렬해 보면 [0, 1, 2, 2, 3]이다.

예시 1에서는 2개의 집중국이 있다고 한다.

 

즉, 가장 거리가 먼 3을 제외시킬 수 있게 된다.

집중국의 개수(k) - 1만큼의 가장 큰 거리를 제외할 수 있는 것이다.

따라서 집중국의 수신 가능영역의 최소 거리합은 0 + 1 + 2 + 2 = 5가 된다.

 

집중국의 개수가 3개라고 가정해 보자.

그렇다면 가장 큰 2개의 거리를 건너뛸 수 있게 된다.

즉, 2가지 경우가 나올 수 있게 된다.

결론적으로 최소 거리합은 0 + 1 + 2로 3이 된다.

코드

fun main() {
    println(solve())
}

private fun solve(): Int {
    val n = readLine()!!.toInt()
    val k = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }.sorted()

    if (k >= n) return 0

    val diff = mutableListOf<Int>()
    for (i in 1 until list.size) diff.add(list[i] - list[i - 1])
    diff.sort()
    
    return diff.slice(0 .. diff.size - k).sum()
}