[Gold IV][JAVA]2110번: 공유기 설치

https://www.acmicpc.net/problem/2110
이분탐색

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

풀이방법

공유기를 두는 최소간격의 최대(mid)를 구해야 한다.

• house[] 에 N개의 집 위치를 저장합니다. 

• 공유기 설치 간격 최소값과 최대값을 구하여 min, max에 저장합니다
  최소값 1을 min에 저장합니다.
  최대값 (house[N-1] - house[0])을 max에 저장합니다.
  Input 1 2 4 8 9
  min => 1
  max => 9 - 1 = 8

• 설치 가능 여부를 탐색
  C이상 설치가 가능하다면
  min = mid + 1;
  C이상 설치가 불가능하다면
  max = mid - 1;

나의 어이없는 실수

배열 범위 N+1이라고 지정해서 값이 4가 나왔다
N+1
[0, 1, 2, 4, 8, 9]
N
[1, 2, 4, 8, 9]

package baekjoon_java.GoldIV;

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

public class 공유기설치 {//2110번 이분탐색
    static int N, C;
    static int[] house;

    public static void main(String arg[]) 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]; //실수 주의

        for (int i = 0; i < N; i++)
            house[i] = Integer.parseInt(br.readLine());
        Arrays.sort(house);

        int result = BSearch(house, C);
        System.out.println(result);
        br.close();
    }

    public static int BSearch(int[] arr, int c) {
        int min = 1; // 최소길이
        int max = arr[arr.length - 1] - arr[0];// 최대길이
        int dis = 0;

        while (min <= max) {
            int mid = (min + max) / 2;
            int cnt = 1; // 공유기 설치 개수
            int previous = arr[0]; //최근에 공유기를 놓은 집

            for (int i = 1; i < arr.length; i++) {
                if (arr[i] - previous >= mid) {//(최소거리)최근 공유기를 놓은 집부터 다음 타켓 까지의 거리
                    cnt++;
                    previous = arr[i];
                }
            }

            if (cnt >= c) {
                // 실제 설치될 공유기보다 많이 설치함 -> 오른쪽으로 이동해 더 긴 간격 찾아야함
                min = mid + 1;
                dis = mid;
            } else if (cnt < c) {
                // 공유기를 c보다 적게 설치함 -> 왼쪽으로 이동해 더 짧은 간격 찾아야함
                max = mid - 1;
            }
        }
        return dis;
    }
}