29.공유기 설치

📍 문제 설명

💡 접근

설치 거리를 중간점으로 지정해놓고 이분탐색 수행하면 된다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int c;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        c = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        Arrays.sort(arr);
        //공유기 설치거리
        int answer = 0;

        //공유기의 설치거리를 중간점으로 지정
        int lt = 0;
        int rt = arr[n-1]-arr[0];
        while(lt <= rt) {
            int mid = (lt+rt) / 2;
            //해당 거리로 공유기 설치가 가능한지 확인
            //설치가 가능하다면 거리를 더 늘려보기
            if(installRouter(mid, arr)) {
                lt = mid + 1;
                //해당 거리를 기록
                answer = mid;
            }
            //설치가 불가하다면 거리를 더 좁혀보기
            else rt = mid - 1;
        }

        System.out.println(answer);

    }

    private static boolean installRouter(int mid, int[] arr) {
        //첫번째 지점에 일단 공유기 설치
        int cnt = 1;
        //공유기 설치한 집 번호
        int dis = arr[0];

        for(int i = 1; i < arr.length; i++) {
            //설치할 수 있는 위치이면 설치
            if(arr[i] - dis >= mid) {
                cnt++;
                dis = arr[i];
            }
        }
        //설치 가능한 거리라면
        if(cnt >= c) return true;
        return false;
    }
}