백준 1477 휴게소 세우기 Kotlin (이분 탐색)

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

1477번: 휴게소 세우기

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

알고리즘 분류

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

풀이

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

풀이는 다음과 같다.

1. m개의 휴게소를 모두 설치 했을 때 고속도로에 있는 n+m개의 휴게소 사이의 거리, 고속도로 시작과 끝 부분에서 휴게소 사이의 거리의 최댓값이 maxDis라 하자.

2. 우리는 가능한 가장 작은 maxDis를 구해야 하고 maxDis의 범위는 1~999이다. 그럼 s=1, e=999로 범위를 잡고 이분 탐색이 가능하다.

3. 이분 탐색할 때 mid값이 우리가 찾고자 하는 maxDis값이다. mid값을 휴게소가 없는 구간의 최댓값이라 할 때 실제 m개의 휴게소를 짓는 게 가능한지, 가능하다면 mid값을 줄여보고, 불가능하면 mid값을 올려가며 문제에서 요구한 최소 maxDis값을 찾는다.

4. canBuild()함수에서 maxDis가 mid일 때 m개 짓는 게 가능한지 확인한다. 이때 입력으로 주어진 휴게소는 미리 정렬해 두자.

5. 0부터 시작해서 현재 위치에서 주어진 n개의 휴게소로 각각 이동하는데 이 거리가 maxDis보다 크다면 maxDis만큼 떨어진 거리에 하나의 휴게소를 설치한다.

6. 이런 식으로  0, 300, 701, 800, 1000까지 탐색하고, 만약 m개 이상 휴게소를 설치해야 한다면 false를 리턴, m개 이하로 가능하다면 true를 리턴하면 된다.

 

 

코드

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

//n개 휴게소
//m개 더 세우기
//끝이랑 시갖 위치에는 세우지 못함
//m개 모두 지어야 함
//휴게소가 없는 구간의 길이의 최댓값을 최소로(휴게소와 휴게소 사이의 거리)
fun canBuild(maxDis: Int, m : Int , place: IntArray): Boolean {
    var cur = 0
    var cnt = 0
    var idx = 0
    while (idx < place.size) {
        //maxDis보다 먼 거리인 경우 휴게소 설치
        if (place[idx] - cur > maxDis) {
            cur += maxDis
            if (cnt == m) return false
            cnt++
        } else {
            cur = place[idx++]
        }
    }
    return true
}

fun main() = with(System.out.bufferedWriter()) {
    val (n,m,l) = getIntList()
    val tk = StringTokenizer(br.readLine())
    val place = IntArray(n + 1) {
        if (it == n) {
            l
        } else {
            tk.nextToken().toInt()
        }
    }
    place.sort()
    var s = 1
    var e = l - 1
    var answer = 0
    while (s <= e) {
        val mid = (s + e) / 2
        if (canBuild(mid, m, place)) {
            answer = mid
            e = mid - 1
        } else {
            s = mid + 1
        }
    }
    write("$answer")
    close()
}