백준 1477) 휴게소 세우기

 

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

1477번: 휴게소 세우기

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

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

 

 

---

 

문제 이해

 

 

우선 "휴게소가 없는 구간의 길이의 최댓값의 최솟값"은 이분탐색 문제에서 종종 쓰이는 표현인 것 같다.

 

문제의 예시를 살펴보면,

고속도로의 길이가 1000. 현재 휴게소가 200,701,800. 휴게소를 1개 더 세운다.

여기서 휴게소가 없는 구간은 무엇인가?

[200-701], [701-800] 라고 자칫 오인할 수도 있다!

사실 문제 초반에 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지 로 명시돼있다.

고속도로의 길이가 1000이라면 0~1000 이므로,

휴게소가 없는 구간의 길이는 [0-200], [200-701], [701-800], [800-1000] 로 이해해야 한다.

 

구간 길이의 최댓값은 501 [200-701] 이다.

하지만 문제에서 명시했듯이 451에 휴게소를 짓게 되면 251 [200-451], 250 [451-701] 이고,

휴게소가 없는 구간의 길이 중에 최댓값이 된다.

 

 

접근 방법

 

 

1) 이분 탐색의 기본은 left(탐색의 시작), right(탐색의 끝) 을 설정하는 것이다.

 

휴게소가 없는 구간의 길이의 최댓값은 어떤 값이 와도 L보다 작기 때문에

 

left = 0

right = L 이 된다.

 

하지만 문제에서 고속도로의 끝에는 휴게소를 세울 수 없다 했으므로,

 

left = 0

right = L-1 으로 설정하자.

 

 

2) 다음으로 탐색 기준이 되는 mid 값을 설정해야 한다.

출력에 나타나 있는 말을 다시 주목해보자.

 

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

 

문제의 결과는 휴게소가 없는 구간의 최댓값이다.

그렇기 때문에 이것이 mid 가 되어야 한다.

 

 

 

mid = (left + right) / 2

 

또한 최솟값을 찾아야 하므로 만약 휴게소를 M개 모두 세울 수 있다면~

 

 

(right - 1을 한 이유는 기존에 있던 mid를 이미 탐색한 것이므로 빼줘야 한다.)

 

만약 휴게소 M개를 세우는 횟수가 초과됐다면?

mid 값을 더 확장해야 휴게소를 세우는 횟수를 줄일 수 있으므로~

 

 

 

 

3) mid 를 설정했다면 이제 어떻게 최댓값이면서 최솟값을 찾을 수 있을까?

 

mid는 휴게소가 없는 구간의 최대값이면서 최솟값의 기준이다.

(그리고 편의를 위해 다음과 같이 변수로 설정하겠다.)

- diff = (다음 배열의 원소 - 현재 배열의 원소)

 

1. diff > mid 라면 최대 구간의 길이를 구할 수 있는 상태로 접어든다.

2. diff / mid 를 한 몫은 휴게소를 세우는 횟수가 된다.

 

예를 들어 구간의 길이 = 10, mid = 4 라면

총 길이 10 중에서 4 - 6 으로 쪼갤 수 있고, 6은 4보다 크므로 또 다시

4 2 로 쪼갤 수 있다. 그래서 총 2개를 지을 수 있고, 10 / 4 = 2가 된다. 

  

2-1. 여기서 주의해야 할 점은 휴게소가 있는 위치에 다시 세울 수 없는 조건이 있다.

그래서 diff / mid 의 나머지가 0일 때 mid의 위치도 포함된 것이기 때문에 1을 빼줘야 한다.

 

 

 

전체 코드

 

import java.util.*
private lateinit var arr : IntArray
fun main() = with(System.`in`.bufferedReader()) {
    val (n,m,l) = readLine().split(" ").map { it.toInt() }
    arr = IntArray(n+2)
    arr[0] = 0
    arr[1] = l
    val st = StringTokenizer(readLine(), " ")
    for(i in 2 until n+2) {
        arr[i] = st.nextToken().toInt()
    }
    arr.sort()

    var left = 0
    var right = l-1
    var res = 0

    while (left <= right) {
        val mid = (left + right) / 2
        if(isPossible(mid, m)) {
            right = mid - 1
            res = mid
        } else {
            left = mid + 1
        }
    }
    println(res)
}
private fun isPossible(mid : Int, m : Int) : Boolean {
    var cnt = 0
    for(i in 0 until arr.size-1) {
        val data = arr[i+1] - arr[i]
        
        if(data > mid) {
            cnt += if (data % mid == 0) {
                data / mid - 1
            } else {
                data / mid
            }
        }
    }

    return cnt <= m
}