[BOJ] 백준 2110 공유기 설치

출처:  https://www.acmicpc.net/problem/2110

Approach

[탐색] Parametric Search  

[탐색] Parametric Search

Binary Search (이분 탐색)  

Binary Search (이분 탐색)

공유기 3개를 설치 시, {1, 4, 8} or {1, 4, 9}에 설치하면 가장 인접한 두 공유기 사이의 거리 = 3

1 → N까지, 공유기를 설치한 앞집(Prev)과의 뒷집(Next)의 위치가 {최대거리 = 3}을 의미.

 

[2 ≤ N ≤ 200,000]이며,  [1 ≤ xi ≤ 1,000,000,000]이기 때문에 

공유기 설치할 수 있는 모든 Case를 완전탐색하여 최대 거리를 구하면 TLE 발생

 

시뮬레이션

▶ 설치 가능한 공유기 개수 『2』개 ← {1, 8}

    기준 거리(mid)가 크기에 작게 해줄 필요가 있음

 

▶ 설치 가능한 공유기 개수 『3』개 ← {1, 4, 8}

    설치하고자 하는 공유기 개수를 만족하지만 최적의 거리를 위해 left > right 될 때까지 반복

 

 

▶ 설치 가능한 공유기 개수 『3』개 ← {1, 4, 8}

    설치하고자 하는 공유기 개수를 만족하면서 이후로는 left > right 이 되므로 탐색 종료.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
    static int N, C;
    static int[] house;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        house = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            house[i] = Integer.parseInt(br.readLine());
        }
        // 오름차순 정렬
        Arrays.sort(house);
         
        int answer = Integer.MIN_VALUE;
        int left = 1;
        int right = house[N] - house[1];
 
        while (left <= right){
            int mid = (left + right) / 2;
             
            int cnt = 1; // 거리(mid)를 만족하는 집의 개수
            int prev = house[1]; // 첫번째 집부터 시작
            for (int i = 2; i <= N; i++) {
                // 각 집을 순회하면서 X 거리 이상 만큼 집이 떨어진 경우에
                // 공유기를 설치 가능 여부 확인
                if (house[i] - prev >= mid){
                    cnt++;
                    prev = house[i];
                }
            }
            // 간격이 작아 공유기가 많이 설치되었거나,
            // 공유기 개수를 만족했더라도 더 가까운 최소 거리 재탐색
            if (cnt >= C){  
                // 거리를 넓혀줍니다.
                left = mid+1;
                answer = mid;
            }
            // 설정한 기준이 너무 멀어 설치된 공유기 개수가 적은 경우
            else {
                // 거리를 좁혀줍니다.
                right = mid -1;
            }
        }
        // 정답 출력
        System.out.println(answer);
    }
}