백준 2110 공유기 설치 Kotlin (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

풀이

파라메트릭 서치 문제이다.

우리가 찾아야 하는 '가장 인접한 두 공유기 사이의 거리'를 이분 탐색으로 찾자.

그러면 이분 탐색의 범위는 0부터 10억, 즉 s = 0, e = 10억으로 mid = '가장 인접한 두 공유기 사이의 거리' = (s+e)/2이다.

이 mid값이 답이 될 수 있다면 mid를 늘려보고, 아니면 mid를 줄인다.

이때 mid값이 답이 될 수 있는지 체크하려면 우선 input을 오름차순으로 sort하고 mid 만큼의 차이로 공유기를 c개 설치할 수 있다면 정답이 답이 될 수 있는 것이다.

아래 check 함수를 확인하는 게 이해가 빠를 것이다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()


var n = 0
var c = 0
lateinit var input: IntArray

fun check(mid: Int): Boolean {
    var cur = input[0]
    var cnt = 1
    for (i in 1 until input.size) {
        if (input[i] - cur >= mid) {
            cnt++
            cur = input[i]
        }
        if (cnt >= c) return true
    }
    return false
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    getIntList().also {
        n = it[0]
        c = it[1]
    }
    input = IntArray(n){ getInt()}
    //solve
    var s = 0
    var e = 1_000_000_000
    input.sort()
    var answer = 0
    while (s <= e) {
        val mid = (s + e) / 2
        if (check(mid)) {
            answer = mid
            s = mid + 1
        } else {
            e = mid - 1
        }
    }
    //output
    write("$answer")
    close()
}