백준 1477번 휴게소 세우기 - SWIFT

문제

---

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 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개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

 

문제 링크

1477번: 휴게소 세우기

 

 

풀이

---

어떻게 풀 지 정말 많이 고민한 문제인데, 결과는 그리 좋지는 못했다.

 

틀린 풀이

가장 먼저 도전한 방법은 이렇다.

1. 휴게소 위치를 먼저 정렬한 후에 나오는 휴게소들 간의 거리를 구한다.
2. 거리를 정렬한다.
3. 그리고 거리가 가장 먼 값 부터 절반으로 나누어서 다시 거리 배열에 넣어준다.
   배열에 넣어줄 때는 upperBound를 이용해서 넣어줬다.(Swift에는 없는 함수이므로 직접 만들었다.)
4. 이 행동을 M번 반복한 다음, 가장 큰 값을 출력해준다.

하지만 이 방법에는 큰 허점이 있었다.

바로 한 구간에 무조건 한 휴게소만 들어간다는 것이었다.

한 구간에 여러 휴게소가 들어가서 2등분만 되는게 아니라 3등분도 가능하다.

휴게소를 절반으로 나눈 값들을 다른 휴게소 거리와 비슷해서, 절반으로 나눈 값이 다른 휴게소 거리보다 크다면 일단 큐에 넣어줬다.

큐에 들어간 애들은 3등분할 애들이 되는 것이다.

그런데 이렇게 하면 4등분할 애들을 넣어줄 또 다른 큐가 필요해지고, 등분이 많이 될 수록 큐가 그만큼 많이 필요해지기 때문에 이 방법은 구현하다가 말았다.

 

정답 풀이

처음에는 휴게소들 간의 거리와 배열의 인덱스를 중점으로 접근했었는데, 접근 방식을 바꿨다.

먼저 생각한 방식들은 답을 직접 구하기 보다는 간접적으로 구하는 방식이었는데, 이번에는 직접적으로 구하기로 했다.

그래서 최대 거리를 중심으로 값을 구한다.

 

1. 일단 위에서 했던 대로, 휴게소를 정렬한 후에 휴게소 사이의 값들을 배열로 저장해놨다.▼

 

 

2. 그리고 가장 왼쪽을 1, 가장 오른쪽을 고속도로 길이 - 1로 두었다.

고속도로 맨 끝은 휴게소를 설치할 수 없기 때문이다.

현재 예시에서는 고속도로 길이가 800이므로 가장 오른쪽은 799가 된다.

이 두 값이 최대거리의 범위가 될 것이다.

여기서 우리는 이 범위를 절반씩 잘라서 값을 확인해볼 것이다.

그러므로 중간값도 같이 구해준다.▼

 

 

3. 방금 구한 중간값으로 휴게소들의 거리를 나눠본다.

중간값으로 휴게소들의 거리를 나눈 값이 설치할 휴게소 개수가 된다.

만약 정확히 나누어 떨어진다면 기존 휴게소와 겹치게 되는 것이므로 값을 하나 빼준다.

이렇게 설치할 휴게소 개수를 전부 더해서 문제에서 제시한 휴게소 개수와 비교해본다.▼

 

 

예제에서는 휴게소를 7개 설치하라고 했는데, 구한 휴게소 개수는 0개로 휴게소를 더 많이 설치해야한다.

따라서 거리 범위를 400미만으로 변경한다.▼

 

 

4. 변경된 거리 범위를 토대로 다시 위에서 했던 작업을 해준다.

중간값으로 전부 나눠서 그 몫을 더해보면 이번에도 설치할 휴게소 개수보다 적다.▼

 

 

따라서 이번에도 거리 범위를 중간값 미만으로 변경한다.▼

 

 

5. 위의 과정을 다시 반복한다.

이번에도 부족하지만, 휴게소 개수가 늘어난 것을 볼 수 있다.▼

 

 

그래도 부족한건 사실이므로, 이번에도 거리 범위를 중간값 미만으로 변경한다.▼

 

 

6. 똑같이 반복해주는데, 이번에는 값이 설치할 휴게소 수보다 크다.

그렇다는 것은 값의 범위를 작은 쪽이 아니라 더 큰 쪽을 볼 때가 됐다는 것이다.▼

 

 

이번에는 거리 범위를 중간값 초과로 변경해준다.▼

 

 

7. 이 이후로는 앞에서 나왔던 과정들의 반복이다.

이 과정들을 왼쪽이 오른쪽보다 크거나 같아질 때 까지 반복해주면, 답이 나오게 된다.▼

 

 

Swift 코드

---

let NML = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = NML[0], M = NML[1], L = NML[2]
var R = [Int]()
var D = [Int]()

R = readLine()!.split(separator: " ").map { Int(String($0))! }
R.sort(by: >)
for i in 0..<N - 1 {
    D.append(R[i] - R[i + 1])
}
D.append(R[N - 1])
D.append(L - R[0])
D.sort(by: <)

var left = 1
var right = L - 1

while left <= right {
    let mid = (left + right) / 2

    var new = 0
    for i in 0..<N + 1 {
        new += D[i] / mid
        if D[i] % mid == 0 {
            new -= 1
        }
    }
    if new > M {
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(left)