[백준 2110번] [Kotlin] 공유기 설치

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

2110번: 공유기 설치

 

난이도 : 골드 4
태그 : 이분 탐색, 매개 변수 탐색

 

 

설명

꽤 오랜 시간을 고민했습니다... 도대체 어떻게 풀어야 하지?

결국 알고리즘 분류를 눌러보고 '이분 탐색'과 '매개 변수 탐색' 두 키워드를 발견했습니다

아, 랜선 자르기와 나무 자르기와 같이 매개 변수, 즉 center를 공유기의 최대 거리로 잡은 이분 탐색이였습니다.

다만 조금 더 매콤한.

 

문제의 예제를 갖고 와 봤습니다. 하지만 먼저, 사용하기 전에 정렬을 해야겠네요.

1 2 4 8 9 정렬된 배열이며, m은 3 입니다.

left = 1, right = 8(마지막 집 - 첫 번째 집)

첫 번째 center는 (1 + 8) / 2 = 4(소숫점 절삭) 입니다.

각 공유기의 거리가 4라 생각해봅시다.

공유기의 거리가 최대가 되려면, 1번째 집은 무조건 설치해야 합니다.

거리가 1(1번째), 8(4번째)인 집에 설치할 수 있으며, 더 이상 공유기를 설치할 수 없습니다.

설치 개수인 3개 보다 적으므로, 각 공유기의 거리가 더 짧아져야 합니다.

즉, right를 center + 1로 하향조정 합니다.

 

left = 1, right = 5

두 번째 center는 (1 + 5) / 2 = 3 입니다.

각 공유기의 거리가 3일 때,

1번째 집(거리 1), 3번째 집(거리 4), 4번째 집(거리 8)에 설치할 수 있습니다.

 

해당 예시로는 표현되지 않으나,

left 값이 상향조정되며 m개의 공유기를 설치할 수 있으면서 더 긴 거리를 찾을 수 있기 때문에,

left  <=  right인 조건 동안 이진 탐색을 계속하며, 최대 거리를 갱신하여야 합니다.

 

 

 

 

소스코드

import kotlin.math.max

fun main() = with(System.`in`.bufferedReader()) {
    val (n, c) = readLine().split(" ").map { it.toInt() } // 집 개수, 공유기 수
    val arr = Array(n) { readLine().toLong() }
    arr.sort()

    var left = 1L
    var right = arr[n - 1] - arr[0]

    var maxDistance = 0L

    // 이진 탐색
    while (left <= right) {
        val targetDistance = (left + right) / 2

        // 설치할 수 있는 공유기 개수 계산
        var installableCnt = 1
        var prev = arr[0]

        for (i in 1 until n) {
            if (arr[i] - prev >= targetDistance) {
                installableCnt++
                prev = arr[i]
            }
        }

        if (installableCnt >= c) {
            // 설치한 공유기가 설치해야 하는 공유기보다 많을 때
            left = targetDistance + 1
            maxDistance = max(maxDistance, targetDistance)
        } else {
            // 설치한 공유기가 설치해야 하는 공유기보다 적을 때
            right = targetDistance - 1
        }
    }

    println(maxDistance)
}

 

위의 코드를 그대로 표현한 것 입니다.

이진 탐색을 진행하며 매 반복마다 설치할 수 있는 집의 개수를 계산하는게 포인트라 할 수 있습니다.

 

 

후기

이진탐색을 쉽게 떠올리지 못해 좀 헤맸던 문제입니다.

DP인가..? 브루트포스/그래프탐색은 100퍼 시간초과 일 것 같은데... 하면서 머리를 싸맸는데,

문제를 보고 어떤 유형인지 파악하는 스킬도 필요할 것 같네요.