(Kotlin) 백준 2110 - 공유기 설치

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

2110번: 공유기 설치

 

풀이

문제가 실버라서 얕봤다가 크게 다쳤다. 조건 자체를 이해하기 어려웠는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하라는 말이 와닿지 않았다. 가장 인접한, 최대 거리??

그래서 마이구미님 블로그(https://mygumi.tistory.com/301)를 참고해서 이해할 수 있었다.

 

위 말을 맥락적으로 해석하면, 최대한 공평하면서도 간격이 크게 공유기를 설치하라는 것이다. 특정 두 집의 사이의 설치 간격이 너무 커지면, 그만큼 나머지 설치된 집들 사이의 간격은 짧아져서 가장 인접한 설치 거리가 짧아지기 때문이다.

 

즉, 거리가 가장 가까운 두 공유기 사이의 거리를 k라고 하면, 나머지 인접한 공유기들 사이의 모두 k보다 크거나 같아야 한다.

ex) k = 3,  2 <-> 5 <-> 12 <-> 15 <-> 19  - (공유기가 설치된 위치)

                         3        7           3           4          - (사이 거리) --> 모두 3보다 크거나 같다

 

이 문제는 이분 탐색의 응용인 파라메트릭 서치를 통해서 해결하는 문제로 알려져 있는데, 방법은 다음과 같다.

1. 가장 인접한 공유기 사이의 거리를 대상으로 이분탐색을 진행한한다.

2. 그 거리보다 크거나 같도록하는 기준을 만족시키면서 왼쪽 집부터 공유기를 설치하면서 갯수를 센다. 

3. 문제에서 주어진 공유기의 개수와 설치한 공유기의 개수를 비교해서, 같거나 더 많이 설치했다면 간격을 늘리고, 더 적게 설치했다면 간격을 줄인다.

4. left(lower) <= right(upper)일 때까지 1~3번을 반복하여 가장 인접한 설치 거리의 상한선을 찾는다.   

 

여기서 이해가 안갔던 건 왜 왼쪽 집부터 항상 공유기를 설치하느냐는 것이었다. 정확하게 증명하려면 약간의 수학이 필요한듯 한데, 자세한 건 https://www.acmicpc.net/board/view/50802를 참고해보자.

  

 

코드

fun main(){
    var n = 0
    var c = 0
    val listOfHouse = mutableListOf<Int>()

    readLine()!!.trim().split(" ").map{ it.toInt() }.let{
        n = it[0]
        c = it[1]
    }

    repeat(n){
        listOfHouse.add(readLine()!!.toInt())
    }
    listOfHouse.sort()	// 정렬: 이분탐색의 전제 조건

    var lower = 1	// 최소 간격
    var upper = listOfHouse.last() - listOfHouse[0]	// 최대 간격: 양 끝 집 사이의 거리
    var answer = upper

    while(lower <= upper){
        val mid = (lower + upper) / 2
        var count = 1			// 공유기 설치한 횟수
        var prevHouseIdx = 0	// 직전에 설치된 집

        // mid보다 인접 간격이 길거나 같도록 설치한다
        for(i in 1 until n){
            if (listOfHouse[i] - listOfHouse[prevHouseIdx] >= mid){
                count++
                prevHouseIdx = i
            }
        }
        
        // c == count -> 간격을 더 늘려도 모두 설치할 수 있는지 확인해본다
        // c < count -> 더 많이 설치됐다 -> 설치 간격을 늘려본다
        if (c <= count){
            lower = mid + 1
            answer = mid
        }else{			// 더 많은 공유기를 설치해야 한다 -> 간격을 줄인다
            upper = mid - 1
        }
    }

    println(answer)
}