문제
다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 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
6 7 800
622 411 201 555 755 82예제 출력 1
70예제 입력 2
3 1 1000
200 701 800예제 출력 2
251예제 입력 3
3 1 1000
300 701 800예제 출력 3
300문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ1477 {
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[] rest=new int[N+1];
boolean[] flag=new boolean[1001];
st=new StringTokenizer(br.readLine());
for(int i=0; i<N;i++){
rest[i]=Integer.parseInt(st.nextToken());
flag[rest[i]]=true;
}
rest[N]=L;
Arrays.sort(rest);
int left=1;
int right=L-1;
while(left<=right){
int mid=(left+right)/2;
int cnt=(rest[0]-1)/mid;
for(int i=1;i<N+1;i++){
cnt+=(rest[i]-rest[i-1]-1)/mid;
}
if(cnt<=M){
right=mid-1;
}
else{
left=mid+1;
}
}
System.out.println(left);
}
}이전에 포스팅한 공유기 설치 문제의 방식을 이용하여 문제를 풀 수 있다.
M개의 공유기를 설치했을 때 공유기 사이의 거리를 최대한 비슷한 간격으로 놓을 수 있도록 하는 문제로 구간을 나누어 생각하면 쉽다.
문제에 나오는 예시를 이용해보자
3 1 1000
200 701 8001 ~ 200
201 ~ 701
702 ~ 800
801 ~ 999
위와 같이 네 구간으로 나누고 각 구간에서 답이 될 수 있는 공유기 사이의 거리값으로 나누면 해당 구간에서 설치할 수 있는 공유기의 개수를 구할 수 있다.
이분탐색 코드를 보며 설명하자면 다음과 같다.
이분탐색
int left=1;
int right=L-1;
while(left<=right){
int mid=(left+right)/2;
int cnt=(rest[0]-1)/mid;
for(int i=1;i<N+1;i++){
cnt+=(rest[i]-rest[i-1]-1)/mid;
}
if(cnt<=M){
right=mid-1;
}
else{
left=mid+1;
}
}
System.out.println(left);mid를 공유기 사이 거리의 최대값으로 정하고 해당 구간마다 mid 값으로 나누어 해당 구간에 설치될 수 있는 공유기의 개수를 구한다.
즉, 위 예제에서 mid 값이 251 이라면 두번째 구간에서 200 - 451 - 701 위치에 공유기가 설치되어 해당 구간에서 공유기 사이의 거리값은 251, 250으로 251이 공유기 사이의 최대값이 된다.
그리고 모든 구간에서 251의 mid값으로 나누어 공유기가 설치될 수 있는지 판단하고 추가로 설치되는 공유기 개수 cnt를 구한다.
cnt 값이 M보다 작거나 같다면 mid값의 범위를 줄여서 공유기를 더 설치하게 하거나 공유기 사이 거리의 최소값을 구해본다.
반대로 M보다 크다면 거리값을 더 크게 만들어볼 수 있기 때문에 mid 범위를 키운다.
이 과정을 반복하면 공유기 사이 거리의 최대값의 최소값을 구할 수 있다.
구간을 나누어 공유기 개수를 구하는 것까지는 생각해냈으나 if문을 묶는 방법을 반대로 해서 답이 나오지 않았다. cnt값이 M보다 작거나 같음을 묶어야하는데 크거나 같다고 묶었더니 답이 다르게 나왔다.
답이 최소값인지 최대값인지 잘 체크하고 판단하면서 문제를 풀어야할 것 같다.
