[BOJ] 2110 공유기 설치 - JAVA

1. 문제

2110번: 공유기 설치

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

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

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

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

---

2. 풀이

• 이 문제는 적합한 간격을 찾는 게 포인트다. 간격은 이분 탐색으로 구한다.
• 그림과 내 코드는 0부터 (가장 끝집 위치)으로 시작했지만, 사실 1부터 (가장 끝집 위치-가장 첫 번째 집 위치)로 시작해도 된다. 그게 더 적게 걸릴 것이다.
• 공유기를 몇 대 설치할 수 있는지 구하는 과정은 다음과 같다.
  
  • 1) 첫번째 집 위치를 prev에 담는다. 
  • 2) 두번째 집부터 마지막 집까지 탐색한다. 이 때, i번째 집-prev가 간격(mid)보다 크거나 같다면 공유기를 설치하고(count++) prev를 i번째 집으로 교체한다.
  • 3) 공유기 개수(count)가 C보다 많거나 같다면 공유기 수를 더 줄여도 된다(=간격을 늘려도 된다)는 의미다. 따라서 min값을 mid+1로 바꾸고 다시 탐색한다.
  • 4) 공유기 개수(count)가 C보다 적다면 공유기 수를 더 늘려야 한다(=간격을 좁혀야 한다). max값을 mid-1로 바꾸고 다시 탐색한다.
• min값이 max보다 커진다면 반복을 멈추고, max를 출력한다.

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

public class BOJ_2110_공유기설치 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.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(in.readLine());
      Arrays.sort(houses);

      int min=0,max = houses[N-1];
      int mid,count;
      while(min<=max){
         mid = (min+max)/2;
         count=1;
         int prev = houses[0];//직전 집
         for(int i=1;i<N;i++){//1부터 끝까지 집 탐색
            if(houses[i]-prev<mid) continue;//지금집-직전 집<간격이면 필요없음
            count++;//지금집-직전집>=간격이면 공유기설치함. count+1, 직전집을 지금집으로 교체
            prev = houses[i];
         }

         if(count>=C) min = mid+1;//공유기가 많으면 더 줄여도됨->간격 늘려야됨
         else max = mid-1;//공유기가 적으면 더 늘려야함->간격 줄여야됨
      }

      System.out.println(max);//최대값
   }
}

---

3. 결과