오늘 풀어볼 문제는 휴게소 세우기 이다!
1. 문제요약
- 현재 일직선 고속도로에 휴게소 N개가 있고, 모든 휴게소를 방문한다.
- 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)
- 휴게소 세울 수 있는 조건
-- 휴게소가 있는 곳에 휴게소를 또 세울 수 없다.
-- 고속도로의 끝에도 휴게소를 세울 수 없다.
-- 휴게소는 정수 위치에만 세울 수 있다.
2. 문제 접근
처음에는 휴게소가 없는 거리들을 모두 우선순위 큐에 넣고, 해당 거리들을 가장 큰 순으로 나열한 뒤 하나씩 꺼내어 그 중간 거리에 휴게소를 세우고자 했다.
그런데! 이렇게 하면 해당 문제는 절대 통과할 수 없다.
다음과 같은 반례를 보자.
해당 도로에 추가되어야 할 휴게소는 2개라고 가정한다.
( [ ] = 휴게소 / -NN- = 거리 )
2.1 반례 케이스
[0]---200---[200]------501------[701]--99--[800]---200---[1000]
여기서 가장 긴 구간은 501이다. 만약 원래 내 방식대로 하게 된다면 아마 다음과 같은 휴게소가 세워질 것이다.
2.2 나의 방식
- 첫 번째 추가 휴게소
[0]---200---[200]--250--[450]--251--[701]--99--[800]---200---[1000]
- 두 번째 추가 휴게소
[0]---200---[200]--250--[450]--126--[576]--125--[701]--99--[800]---200---[1000]
도출된 정답 : 250
2.3 반례
[0]---200---[200]--166--[366]--166--[532]--169--[701]--99--[800]---200---[1000]
도출된 정답 : 200
즉 나의 방식에서는 긴 구간 내에 여러개의 휴게소를 두어, 도로의 최대 길이를 줄여야 하는 경우를 반영하지 못한다.
이런 문제는 어떻게 풀어야 하는가? 바로 이분탐색이다. 정확하게는 "PARAMETIC SEARCH"를 이용하는 것이다. 해당 알고리즘은 무엇인가!
3. parametric search (매개 변수 탐색)
파라매트릭 서치는 이분 탐색과 굉장히 유사하다. 차이점은 다음과 같다.
'최적화 문제를 결정 문제로 바꾸어 푸는 것!'
예시를 통해 알아보자.
3.1 문제
자동차를 탈 수 있는 사람 중 나이가 가장 어린 사람을 찾아보자.
이때 자동차를 탈 수 있는 사람이라 함은 나이가 19세 이상이라고 가정한다.
(즉 19세 이상은 모두 탈 수 있다.)
가장 어린 사람의 번호는 몇 번일까? 이때 사람이 나열되어있고, 이 사람들은 나이순으로 정렬되어 있다.
3.2 접근법
해당 문제를 결정문제로 바꿔보자!
자동차를 탈 수 있는가?
만약 해당 문제가 이 질문만으로 해결이 가능하다면, 파라메트릭 서치를 정확히 사용한 것이다.
파라메트릭 서치는 이분탐색과 굉장히 유사하므로, left, right, mid를 사용해줄 것 이다.
3.3 풀이
첫 번째 위의 그림에서 5번 사람이 자동차를 탈 수 없다고 했다.
전체에서 이미 나이순으로 정렬되어 있다고 하였으니, 이제 5번 이하 사람들은 모두 정답 범위에서 벗어난다.
7은 자동차를 탈 수 있다고 한다.
이 말은 즉슨, 7번 이상의 사람들 역시 모두 자동차에 탈 수 있다는 것이다.
그렇다고 7번이 자동차를 탈 수 있는 가장 어린 사람인가? 그렇지 않다. 우리는 왼쪽으로 더 탐색해봐야 한다.
L과 R과 M이 모두 같은 번호를 가리킨다. 만약 해당 6번이 자동차를 탈 수 있다고 답한다면, 정답은 7이 아닌 6이 된다.
만약 6이 자동차를 탈 수 없다고 답했다면, 당연히 답은 7번이 되는 것이다.
3.4 시간 복잡도
이분탐색 처럼 L,R을 두고 반틈씩 줄여가며 판단한다.
즉 시간복잡도는 O(logN)의 복잡도이다.
4. 풀이
이제 파라메트릭 서치에 대해 알았으니, 이 문제도 결정 문제로 바꿔보자.
우리는 다음과 같은 질문을 던질 수 있을 것이다.
"최대 구간 길이를 X 이하로 만들면서, M개 이하의 휴게소로 해결할 수 있는가?"
왜 이 질문이 적절한가?
1) X(최대 구간 길이)를 먼저 정한다.
- 예를 들어, X = 300이라고 가정하면,
→ "모든 구간의 길이를 300 이하로 유지하려면 M개 이하의 휴게소로 가능할까?"
모든 구간을 X 이하로 만들기 위해 필요한 휴게소 개수를 계산한다.
2) 각 구간을 나눠야 하는 개수를 계산하고, 그 합이 M(추가해야 할 휴게소 개수) 이하인지 확인.
- M개 이하라면 X를 줄여서 더 나은 해를 찾는다.
- M개를 초과하면 X를 늘린다. (현재 X개를 추가하기엔 구간이 너무 작다는 뜻)
5. 코드
중요한 로직은 다음과 같다.
1️⃣ 탐색 범위 설정
- left = 1 (최소 간격)
- right = L (최대 간격)
2️⃣ 이진 탐색 실행
- mid = (left + right) / 2 를 최대 구간 길이로 설정.
- 질문: "mid 이하로 모든 구간을 나눌 때, M개 이하의 휴게소로 가능한가?"
- 가능하다면 right = mid - 1
- 불가능하다면 left = mid + 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 현재 휴게소 개수
int M = Integer.parseInt(st.nextToken()); // 추가할 휴게소 개수
int L = Integer.parseInt(st.nextToken()); // 고속도로 길이
int[] shelters = new int[N + 2]; // 기존 + 시작점(0) + 끝점(L)
shelters[0] = 0;
shelters[N + 1] = L;
if (N > 0) {
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
shelters[i] = Integer.parseInt(st.nextToken());
}
}
Arrays.sort(shelters); // 오름차순 정렬
int left = 1, right = L, answer = L;
while (left <= right) {
int mid = (left + right) / 2; // 현재 탐색할 "최대 구간 길이"
int count = 0; // 필요한 휴게소 개수
for (int i = 1; i < shelters.length; i++) {
int gap = shelters[i] - shelters[i - 1]; // 현재 구간 길이
count += (gap / mid); // 구간을 mid 크기로 쪼갤 때 필요한 휴게소 개수
if (gap % mid == 0) count--; // 정확히 나누어 떨어지는 경우 보정
}
if (count > M) { // 필요한 휴게소 개수가 너무 많음 -> mid 증가 필요
left = mid + 1;
} else { // 필요한 개수 이하 -> mid 줄여서 더 나은 값 찾기
answer = mid;
right = mid - 1;
}
}
System.out.println(answer);
}
}