휴게소 세우기
문제
다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 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부터 최대 l-1 까지이다. 이 안에서 이진탐색을 통해 값을 구한 후 해당 값이 최댓값의 최솟값인지를 확인해주면 된다.
예를 들어 문제 예시에서 고속도로의 길이가 1000이기 때문에 시작값 = 1, 끝값 = 1000 - 1 = 999를 초기값으로 설정해 둔 후 이진탐색을 통해 정답을 찾는다.
mid값을 정한다면 기존 휴게소 사이에 몇개의 휴게소가 추가 되어야 하는지를 찾는다.
ex. mid = 500 :
0 ~ 200 : 0개 필요
200701 : 1개 필요800 : 0개 필요
701
800~1000 : 0개 필요
다음과 같이 값을 찾았을 때 총 필요한 휴게소의 갯수는 1개이므로 문제에서 원하는 휴게소의 갯수와는 일치한다.
그러나 우리는 최댓값의 최솟값을 찾아야한다.
지금 찾은 500의 값도 가능하지만 그보다 작은 값도 가능한지 확인한다.
즉 mid값이 세우려는 휴게소의 갯수보다 작거나 같다면 mid값을 줄이고
그렇지 않다면 mid값을 늘려 답을 찾아야 한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
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[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
List<Integer> list = new ArrayList<>();
if (n > 0) {
list.add(arr[0]);
list.add(l - arr[n - 1]);
}
if (n == 0) {
list.add(l);
}
for (int i = 1; i < n; i++) {
list.add(arr[i] - arr[i - 1]);
}
int start = 1;
int end = l - 1;
while (start <= end) {
int mid = (start + end) / 2;
int cnt = 0;
for (Integer integer : list) {
cnt += (integer-1) / mid;
}
if (cnt <= m) {
end = mid - 1;
}else{
start = mid + 1;
}
}
System.out.println(start);
}
}
'알고리즘' 카테고리의 다른 글
14719 빗물 (Java) (0) | 2022.05.16 |
---|---|
3079 입국심사 (Java) (0) | 2022.05.13 |
14503 로봇 청소기 (Java) (0) | 2022.05.04 |
17140 이차원 배열과 연산 (Java) (0) | 2022.05.02 |
11727 2xn 타일링 2 (0) | 2022.05.01 |