boj2110 공유기 설치_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)가 한 줄에 하나씩 주어진다.

출력

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

나의 풀이

• 먼저 집들 중에 가장 가까운 거리를 min 과 가장 먼 거리 max 를 구한다.
• 이분탐색으로, 공유기 사이의 거리를 mid 값으로 구하고, 공유기 설치가 가능한 경우만 answer를 갱신하고, 필요한 개수만큼 공유기 설치가 불가능한 경우는 사이 거리가 너무 길다는 의미이기 때문에 right 을 mid-1 로 갱신하고,
  left 를 mid+1 로 갱신한다.
• 핵심 코드

  while(left<=right){
      int mid = (left+right)/2;
      prev = houses[0];
      int cnt = 1;
      for (int j = 1; j < N; j++) {
          int distance = houses[j]-prev;
          if(cnt==C) break;
          if(distance>=mid){
              prev = houses[j];
              cnt+=1;
          }
      }
      if(cnt>=C){
          left = mid+1;
          answer = mid;
      }else{
          right = mid-1;
      }
  
  }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  public class boj2110 {
      public static void main(String[] args) throws Exception{
          BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          int N = Integer.parseInt(st.nextToken());
          int C = Integer.parseInt(st.nextToken());
  
          int[] houses = new int[N];
          for (int i = 0; i < N; i++) {
              houses[i] = Integer.parseInt(br.readLine());
          }
          Arrays.sort(houses);
          int prev = houses[0];
          int min = Integer.MAX_VALUE;
          for (int i = 1; i < N; i++) {
              int gap = houses[i]-prev;
              min = Math.min(min,gap);
              prev = houses[i];
          }
  
          int answer = 0;
          int max = houses[N-1]-houses[0];
  
          if(C==2){
              answer = max;
          }else {
              int left = min;
              int right = max;
              while(left<=right){
                  int mid = (left+right)/2;
                  prev = houses[0];
                  int cnt = 1;
                  for (int j = 1; j < N; j++) {
                      int distance = houses[j]-prev;
                      if(cnt==C) break;
                      if(distance>=mid){
                          prev = houses[j];
                          cnt+=1;
                      }
                  }
                  if(cnt>=C){
                      left = mid+1;
                      answer = mid;
                  }else{
                      right = mid-1;
                  }
  
              }
          }
          System.out.println(answer);
  
      }
  }

결과