BOJ_2110 : 공유기 설치

👉 문제링크

2110번: 공유기 설치

---

---

🔸 문제 분석 🔸

• N개의 수직선 위 집들의 좌표가 입력으로 주어진다.
  • C개의 공유기를 설치하려는데, 가장 가까운 공유기의 거리를 최대로 하고자 한다.
• 공유기의 거리를 이분탐색과 같은 형태인 매개변수 탐색으로 찾아낸다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        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[] home = new int[N];
        for (int i = 0; i < N; i++) {
            home[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(home);

        int start = 1;
        int end = home[N - 1] - home[0];
        int answer = 0;

        // 집들 사이의 거리 기준으로 이분탐색
        while (start <= end) {
            int mid = (start + end) / 2;
            int cnt = 1;
            int temp = home[0];
            for (int i = 1; i < N; i++) {
                if (home[i] - temp >= mid) {
                    cnt++;
                    temp = home[i];
                }
            }

            // 공유기 거리 늘려서 재설치해보기
            if (cnt >= C) {
                answer = Integer.max(answer, mid);
                start = mid + 1;
            }
            // 공유기 거리 줄여서 재설치 해보기
            else end = mid - 1;
        }
        System.out.print(answer);
    }
}

🔸 코드 해석 🔸

• 입력된 집들의 좌표를 오름차순으로 정렬한다.
• 매개변수 탐색을 진행한다.
  • start는 공유기 사이의 최소거리, end는 공유기 사이의 최대거리이다.
  • 첫 공유기는 첫 번째 집에 놓는다고 가정한다.
  • 반복문에서 공유기 사이의 거리가 mid를 넘지 않는 경우 cnt를 센다.
  • cnt가 C 이상이면, 아직 너무 가깝다는 것이므로 공유기 거리를 늘려보기 위해 start를 mid+1로 증가시킨다.
  • cnt가 C보다 작다면, 너무 멀다는 것이므로 공유기 거리를 줄이기 위해 end를 mid-1로 감소시킨다.

---

🔸 end 🔸

• 문제 풀이 전략이 떠오르지 않아서 풀이를 보면서 클론코딩으로 풀었다.
• 이분탐색이 오랜만이라 어색하면서, 매개변수 탐색은 너무 생소해서 풀이를 이해하기도 어려웠던 것 같다.