[백준/2110] 공유기 설치(Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/2110
• 분류 : 이진탐색
• 풀이 시간 : 30분
  * 문제 이해 시간이 제일 오래걸림;

문제 해설

1. 도현이의 N개의 집은 수직선 위에 설치되어있음
2. 집에 공유기 한대씩 설치해서, 총 C개의 공유기 설치하려고 함
3. 공유기를 적당한 거리를 두고 각 집에 설치
4. 적당한 거리 중 최대 값은?

Solution

풀이 접근 방법

1. 공유기를 적당한 거리를 두고 설치
   • 공유기간의 거리 차가 1, 2, 3, ... (최대) 일 때 각각 몇개의 공유기 설치 할 수 있는지 확인
     • 거리 차 최소 : 1, 최대 : 가장 거리가 먼 집 - 가장 가까운 집
       • 집의 좌표 배열을 오름차순 정렬하여 구함
   • 모든 경우의 수를 다 해보면 $O(n^2)$
   • 좀 더 효율적인 연산을 위해 이진 탐색 구현

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
  static int N, C;
  static int[] home;
  static int answer = -1;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] info = br.readLine().split(" ");

    N = Integer.valueOf(info[0]);
    C = Integer.valueOf(info[1]);
    home = new int[N];

    for (int i = 0; i < N; i++) {
      home[i] = Integer.valueOf(br.readLine());
    }

    // 집 위치 좌표 오름차순 정렬
    Arrays.sort(home);

    // 매개변수 : 위치 차의 최소, 최대
    binarySearch(1, home[N - 1] - home[0]);

    bw.write(answer + "\n");
    bw.flush();
    bw.close();
  }

  static void binarySearch(int start, int end) {
    if (start > end)
      return;

    int mid = (start + end) / 2;
    // mid 거리 차로 몇개의 공유기를 설치할 수 있는지 계산
    int count = install(mid);

    // 기준만큼 || 기준보다 더 설치할 수 있으면
    if (count >= C) {
      answer = Math.max(answer, mid);
      // 거리 차를 넓혀본다
      binarySearch(mid + 1, end);
    } else if (count < C) {
      // 기준보다 더 적게 설치 = 간격이 너무 큼 -> 간격줄이기
      binarySearch(start, mid - 1);
    }
  }

  static int install(int interval) {
    int flagHome = home[0];
    int count = 1;

    for (int i = 1; i < N; i++) {
      // 공유기 설치된 집 + 거리 차이 = 다음 공유기가 설치될 수 있는 최소 위치
      if (flagHome + interval <= home[i]) {
        count++;
        flagHome = home[i];
      }
    }

    return count;
  }
}