백준 2110 공유기 설치 Java

이분탐색 문제인 공유기 설치 문제이다.

난 문제를 이해하는 것도 헷갈렸다.. 요즘 문제 이해하기가 넘 힘들다..

문제의 요점은 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하는 것인데

예제에서는 3개의 공유기를 설치하고

1 2 8 4 9 에서 최대 거리가 3이다.

나는 1 4 9 에 설치하면 최대 거리가 5인데?.. 이러고 있었다.

 

문제는 그게 아니라

공유기 3개를 설치할 때 최대 거리가 3인 이유는

1에 설치

4에 설치

7이상에 설치가 가능한데

8과 9가 있으니

3개가 설치가 가능하고 그 최대 거리가 3인 것이다.

만약 최대 거리가 4이면

1 -> 설치

2 -> 설치 불가

4 -> 설치 불가

8 -> 설치

9 -> 설치 불가(8에서 설치했으니 13이상의 수만 설치가능)

정리하자면 마지막으로 설치한 곳 + 최대거리로 공유기 c개를 설치하는 것이였다.

 

그렇다면 랜선 자르기, 나무 자르기 문제처럼

가능한 거리의 범위를 구하고

이분 탐색으로 그 범위를 좁혀나가는 전형적인 방식으로 문제를 풀면 된다.

 

이 문제같은 경우엔

가능한 거리의 시작 값인 start는 1이다.

거리는 무조건 1이상 차이가 나기 때문이다.

가능한 거리의 마지막 값인 end는 집의좌표의 마지막 값 - 첫번째 값이다.

집의좌표에서 가장 멀리있는 값과 가장 가까이 있는 값의 차이가 가장 멀리 떨어질 수 있는 거리이기 때문이다.

 

이렇게 범위를 설정하려면 일단 입력받은 집들의 좌표값을 정렬해줘야 한다.

그리고 그 배열의 가운데 값인 mid를 기준으로

공유기를 c이상 설치가 가능한지 체크한다.

 

c이상 설치가 가능하다면

start = mid+1;

c이상 설치가 불가능하다면

end = mid-1;

이런 식으로 값의 범위를 좁혀가고

c이상 설치가 가능할 때의 mid값들 중 최대값을 출력하면 된다.

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Q2110 {
    
    static boolean check(int[] a, int dist, int c) {
        int cnt = 1;
        int last = a[0]+dist; //첫 번째 값 + 거리
        for(int i=0; i<a.length; i++) {
            if(a[i] >= last) {
                cnt++;
                last = a[i]+dist; //마지막 값 + 거리
            }
        }
        return cnt >= c;
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int c = scan.nextInt();
        int [] a = new int[n];
        
        for(int i=0; i<n; i++){
            a[i] = scan.nextInt();
        }
        
        Arrays.sort(a);
        int ans = 1;
        int start = 1;
        int end = a[n-1]-a[0]; //가능한 최대 거리
        
        while (start <= end) {
            int mid = (start+end)/2;
            if (check(a, mid, c)) {
                ans = Math.max(ans,mid);
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
        System.out.println(ans);
    }
}