[백준] 2110번 공유기 설치 Java

문제 링크

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

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

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

알고리즘: 이분 탐색

풀이

이 문제는 설치한 공유기 사이 거리 중 최소인 값이 최대가 되게끔 만들어야 한다.
최소 거리를 1로 설정하고(최소 거리가 1인 이유는 집 사이 거리가 최소 1이기 때문),
최대 거리를 맨 끝에 위치한 집 - 첫 번째 위치한 집으로 설정한다.
여기서 중간값을 mid_dist라 하고 mid_dist값으로 공유기를 설치했을 때,

1. 공유기 개수가 C값보다 같거나 크면 최소 거리를 mid_dist로 설정해준다.
   -> 아직 mid_dist가 정답인지 확정 지을 수 없음

2. 반대로 공유기 개수가 C값보다 작다면 최대 거리를 mid_dist - 1로 설정해준다.
   -> mid_dist값은 정답이 될 수 없으므로 mid_dist - 1로 설정.

1,2번을 min_dist == max_dist가 될 때까지 반복한다.
그러면 우리가 원하는 설치한 공유기 사이 거리 중 최소인 값이 최대가 되는 값을 구할 수 있다.

시간 복잡도를 계산해 보면 공유기 설치 N번, 인접한 두 공유기 사이의 최대 거리 찾는데
log2N번(이분 탐색) 해서 N*log2N이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N,C;
    static long home[];
    static long max_dist, min_dist;
    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());
      home = new long[N];
      for(int i=0; i<N; i++) {
          home[i] = Long.parseLong(br.readLine());
      }
      Arrays.sort(home);
      min_dist = 1;
      max_dist = home[home.length-1] - home[0];
      while(min_dist != max_dist) {
          long mid_dist;
          //mid_dist 구하기
          if((min_dist + max_dist)%2 == 0) mid_dist = (min_dist + max_dist)/2;
          else mid_dist = (min_dist + max_dist)/2 + 1;
          //공유기 설치
          int cout = 1;
          long last_router = home[0];
          for(int i=1; i<N; i++) {
              if(last_router + mid_dist <= home[i]) {
                  last_router = home[i];
                  cout += 1;
              }
          }
          if(cout >= C) {
              //min_dist 업데이트
              min_dist = mid_dist;
          } else {
              //max_dist 업데이트
              max_dist = mid_dist - 1;
          }
      }
      System.out.println(min_dist);
    }
}