[백준] 2110번 공유기 설치 문제 이분탐색으로 쉽게 풀어보기
1. 문제
문제는 위의 링크를 클릭하면 확인할 수 있다.
2. 풀이
이 문제 또한 이분탐색으로 해결할 수 있다. 공유기 사이의 거리를 이분탐색을 통해 구해보면서 c 개를 설치할 수 있는 거리가 어디인지를 찾아보는 것이다.
이분탐색의 경우에는 초기의 left 와 right 값을 잘 정하는 것이 중요한데 여기서는 left의 값은 1로 잡고 (가장 최소의 값이 거리 1이기 때문) right의 값은 집의 위치를 정렬한 다음에 가장 끝 집과 첫 집의 거리로 잡으면 된다. (이것이 거리의 가장 최댓값)
그런다음에 이분탐색을 진행하고,
만약 가장 인접한 두 공유기 사이의 거리를 통해 주어진 공유기 c개를 설치할 수 있다면 left의 값을 mid+1로 조정, 설치할 수 없다면 right의 값을 mid-1로 조정한다.
공유기를 설치할 수 있는지를 판단하는 함수를 하나 만들어주었다.
public static boolean check(int mid){
int count=1;
int first=place[0];
for(int location: place){
if (location-first>=mid){
count++;
first=location;
}
}
return (count>=k);
}여기서 count는 설치할 수 있는 공유기의 개수를 의미하고 기준이 되는 place 의 값을 변경하면서 공유기를 설치할 수 있는지 세어주었다. 만약 count의 값이 문제에서 주어진 c 값보다 크거나 같다면 true를 return 아니면 false를 return 해준다.
위의 check 함수를 이용한 이분탐색 부분의 코드는 아래와 같다.
int ans=1; //거리 최소 1
int left=1;
int right=place[n-1]-place[0]; //최대 거리
while(left<=right){
int mid=(left+right)/2;
if (check(mid)){
ans=Math.max(ans, mid);
left=mid+1;
}
else{
right=mid-1;
}
}여기서 이분탐색을 사용하기 위해서는 반드시 정렬이 된 상태여야 하기 때문에 문제에서 입력받은 place를 먼저 정렬한 뒤 사용해야 한다.
3. 코드
이를 활용한 전체 코드는 아래와 같다.
import java.util.*;
public class Main{
static int k;
static int []place;
public static boolean check(int mid){
int count=1;
int first=place[0];
for(int location: place){
if (location-first>=mid){
count++;
first=location;
}
}
return (count>=k);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
k=sc.nextInt();
place=new int[n];
for(int i=0; i<n; i++){
place[i]=sc.nextInt();
}
Arrays.sort(place);
int ans=1; //거리 최소 1
int left=1;
int right=place[n-1]-place[0]; //최대 거리
while(left<=right){
int mid=(left+right)/2;
if (check(mid)){
ans=Math.max(ans, mid);
left=mid+1;
}
else{
right=mid-1;
}
}
System.out.println(ans);
}
}
이분탐색처럼 보이지 않는 문제도 이분탐색을 활용하면 쉽게 해결할 수 있는 경우가 많다. 위의 코드와 비슷한 문제 2805번 나무 자르기 문제도 그 예시중 하나다.