[JAVA] 백준 2110 - 공유기 설치

문제

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

2110번: 공유기 설치

해결 방법

• 일단 문제를 이해하는 것도 조금 헷갈려서 문제부터 정리해 봄
• 집 주소로 [1, 2, 4, 8, 9]가 들어오고 공유기 개수가 3개로 들어왔을 때 왜 정답이 3일까?

1. 최대 거리가 1이라면 => [1, 2, 4, 8, 9] 5개의 집에 공유기를 설치해야 됨
2. 최대 거리가 2라면 => 1번집에 공유기를 설치하면 2번집에는 설치하지 않아도 됨 => ... => [1, 4, 8] 3개의 집에 공유기를 설치해야 됨
3. 최대 거리가 3이라면 => [1, 4, 8] 3개의 집에 공유기를 설치해야 됨
4. 최대 거리가 4라면 => 1번집에 공유기를 설치하면 4번집까지는 설치하지 않아도 되고 8번집에 설치 -> ... -> [1, 8] 2개의 집에 설치

• 문제에서 주어진 공유기 개수가 3이므로 거리가 2, 3일때 공유기 3개 설치이므로 그 중 최대인 3이 정답이 됨
• 이 문제의 해결 방법은 위에서 했던 방식대로 최대거리를 x로 가정했을 때, 공유기를 입력받은 개수 이상으로 설치할 수 있느냐를 확인하고 가능한 x중 최대값을 출력하면 됨
• 이 때, 좌표가 최대 10억이므로 x를 순서대로 가정해보면 시간초과가 발생
  • 따라서 x를 가정할 때 반복문이 아닌 이진탐색을 활용해 시간초과 문제를 해결해야 함

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class p2110 {
    static int n, c;
    static int[] arr;

    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());   // 공유기 개수

        arr = new int[n];
        for(int i = 0 ; i < n ; i ++) {
            arr[i] = Integer.parseInt( new StringTokenizer(br.readLine()).nextToken() );
        }
        Arrays.sort(arr);

        // 거리의 최소 : 1, 거리의 최대 : 마지막 집주소 - 처음 집주소
        int ans = binarySearch(1, arr[n - 1] - arr[0]);
        System.out.println(ans);
    }
    static int binarySearch(int left, int right) {
        if(left >= right) {
            return left;
        }

        int mid = (left + right) / 2 + 1;
        int count = 1;

        // temp가 이전 집 주소
        int temp = arr[0];
        for(int i = 1 ; i < n ; i ++) {
            // 이전 집과의 거리가 mid 이상이면 공유기 추가
            if(arr[i] - temp >= mid) {
                count ++;
                temp = arr[i];
                if(count >= c) {
                    // c개 이상 설치되면 뒷부분 return
                    return binarySearch(mid, right);
                }
            }
        }

        // c개 미만 설치되면 앞부분 return
        return binarySearch(left, mid - 1);
    }
}