백준 2110 공유기 설치

임찬형·2022년 7월 20일

코테

문제 팁

목록 보기

5/73

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

문제를 요약하자면, 집의 개수 N과 공유기 개수 C를 입력받아 C개의 공유기를 모두 설치하는 케이스 중 공유기 사이의 최단 거리가 가장 큰 경우의 거리를 출력하는 것이다.

집의 좌표가 0~10억 이므로 이분탐색 냄새가 꽤나 났다.

먼저 위의 테스트 케이스에 대해서 생각해보며 구현 갈피를 잡아보려고 했다.

1, 2, 4, 8, 9 위치에 집이 존재하며 3개의 공유기를 위 집들에 분배한다.

예를 들어 1, 2, 4 위치 집에 공유기를 분배한 경우 공유기 사이의 최단 거리는 1위치의 집과 2위치의 집 사이의 거리인 1이 된다.

만약 1, 4, 9 위치 집에 공유기를 분배한 경우 공유기 사이의 최단 거리는 1위치의 집과 4위치의 집 사이의 거리인 3이 된다.

아직 이러한 이분탐색 문제가 익숙치 않아 구글링을 통한 아이디어를 찾아본 후 풀이하였다.

핵심 풀이방법은 공유기 사이의 최단 거리를 1에서 부터 가장 먼 거리까지 범위로 잡고 이분탐색을 통해 모든 공유기를 설치할 수 있는 최단 거리 중 최댓값을 찾는 것이다.

최단 거리를 1로 가정해보자, 앞쪽 집부터 다음 집까지의 거리가 1 이상이라면 공유기를 하나 설치하며 반복해서 다음 집 사이로 이동한다.
공유기를 모두 사용할 경우 (위에선 3개) 해당 최단 거리는 만족될 수 있음을 알 수 있다.

최단 거리를 8로 가정해 보자, 1위치 집에 설치하고 2, 4, 8 위치는 1 위치로부터 거리가 8보다 작아 설치할 수 없다.
그리고 9 위치에 설치를 할 수 있지만 사용한 공유기가 2개로 한 개 모자라므로 해당 최단 거리는 만족될 수 없음을 알 수 있다.

이러한 방식으로 1부터 가장 긴 간격 사이를 이분 탐색으로 탐색하며 직접 놓아 보고 최대의 간격을 구해볼 수 있다.

이를 구현한 코드는 아래와 같다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, C) = readLine().split(' ').map{it.toInt()}
    val houses = mutableListOf<Int>()

    for(i in 1..N)
        houses.add(readLine().toInt())

    houses.sort()

    var mid: Int
    var low = 0
    var high = houses[houses.lastIndex]

    while(low <= high){
        mid = (low + high) / 2
        if(canInstall(houses, mid, C))
            low = mid + 1
        else high = mid - 1
    }
    print(high)
}

fun canInstall(houses: List<Int>, gap: Int, cnt: Int): Boolean{
    var before = houses[0]
    var exist = cnt - 1

    for(i in 1 until houses.size){
        if(houses[i] - before >= gap){
            exist--
            before = houses[i]
            
            if(exist == 0)
            	return true
        }
    }

    return false
}