이분탐색 / 매개변수 탐색 마스터 하기
👀 문제
1477번: 휴게소 세우기 ✨ 골드 4
다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.
다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.
다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)
예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.
일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.
제한
- 0 ≤ N ≤ 50
- 1 ≤ M ≤ 100
- 100 ≤ L ≤ 1,000
- 1 ≤ 휴게소의 위치 ≤ L-1
- N+M < L
- 모든 휴게소의 위치는 중복되지 않음
- 입력으로 주어지는 모든 수는 정수
예제 입력
6 7 800
622 411 201 555 755 82예제 출력
70🔑 키포인트
이분 탐색 매개변수 탐색
✍️ 코드
1️⃣ 구간의 최댓값이 최소가 되는 길이를 찾는 것이고, 고속도로의 처음과 끝에는 휴게소를 설치할 수 없으므로 start = 1, end = 고속도로의 길이 - 1
2️⃣ 시작점과 첫 휴게소, 마지막 휴게소와 끝 사이의 구간 길이도 알아야 하므로 휴게소 배열에 0과 l도 추가하고 오름차순 정렬
3️⃣ 이분탐색 진행: 구간 사이에 해당 간격(mid)을 가진 휴게소를 몇 개 설치할 수 있는지 확인하기 위해 for문을 돌면서 cnt += dist / mid 진행
4️⃣ cnt > m 이면 간격(구간의 길이)을 더 늘려야 하므로 start = mid + 1, cnt <= m 이면 간격을 더 줄여야 하므로 end = mid - 1 해 주고 answer을 mid(구간 길이)로 갱신
🤔 이때, m이 cnt보다 작아도 더 작은 구간을 가지도록 나머지 휴게소를 다 설치해 버리면 되므로 무조건 정답을 갱신해 줍니다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class BOJ1477_휴게소세우기 {
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()); // 고속도로의 길이
ArrayList<Integer> arr = new ArrayList<>();
arr.add(0);
arr.add(l);
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(st.nextToken()));
}
arr.sort(null); // 휴게소 오름차순 정렬
int start = 1;
int end = l - 1;
int answer = end;
while (start <= end) {
int mid = (start + end) / 2;
int cnt = 0;
for (int i = 0; i < arr.size() - 1; i++) {
int dist = arr.get(i + 1) - arr.get(i) - 1; // 이미 휴게소 있는 위치는 세우지 못하니까 -1
cnt += dist / mid; // 휴게소 그 사이에 몇 개 설치되는지
}
if (cnt > m) {
// 공백 길이 더 늘려야 함
start = mid + 1;
} else {
// 공백 길이 줄여야 함
end = mid - 1;
answer = mid;
}
}
System.out.println(answer);
}
}
