[백준] 2110번 공유기 설치 문제 이분탐색으로 쉽게 풀어보기 : Programming Story

1. 문제

www.acmicpc.net/problem/2110

문제는 위의 링크를 클릭하면 확인할 수 있다.

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번 나무 자르기 문제도 그 예시중 하나다.