이번에 풀어본 문제는
백준 2110번 공유기 설치 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,C;
    static int [] h_point;
    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());

        h_point = new int[N];
        for(int i = 0; i < N; ++i)
        {
            h_point[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(h_point);

        int left = 1; //최소 간격
        int right = h_point[N-1] - h_point[0]; //최대 간격

        while(left <= right)
        {
            int mid = (left + right) / 2;

            if(set(mid) >= C) left = mid+1;
            else right = mid-1;
        }
        System.out.print(left-1);
    }
    static int set(int dist)
    {
        int cur = h_point[0];
        int cnt = 1;
        for(int i = 1; i < N; ++i)
        {
            if((h_point[i] - cur) >= dist)
            {
                cur = h_point[i];
                cnt++;
            }
        }
        return cnt;
    }
}

📝 풀이

각각의 위치를 갖는 N개의 집에 C개의 공유기를 설치하는데, 가장 인접한 공유기간의 거리의 최댓값을 구하는 문제입니다. 시간초과의 우려가 있으므로 이분탐색을 활용했습니다. 집에 공유기를 설치하는것이 기준이 아닌, 출력값으로 선택될 최소 간격값을 기준으로 하여 이분탐색을 진행합니다. 어떤 경우가 주어지든 정답이 될수있는 간격의 최소는 1, 최대는 마지막 집의 좌표 - 첫 집의 좌표가 될 것이므로 둘을 left,right로 초기화 시킨 후 진행합니다.
반복문 내에서 선택된 mid값으로 공유기를 설치했을 때 목푯값인 C보다 작다면 간격을 좁혀 더 많은 공유기를 설치할 수 있도록 해야하며, 반대로 더 크다면 간격을 넓혀야 할 것입니다. 위 과정을 반복한 후 마지막 탈출조건을 충족시킨 left값의 -1을 하여 출력하면 해결할 수 있습니다.

📜 후기

최소 거리를 기준으로 탐색을 진행한다는 접근을 하지 못해서 꽤 어려웠던 문제였습니다. 위와같은 방식을 파라메트릭 서치라고 하는데, 결과를 기준으로 접근하는 것에 대해 좀 더 공부해봐야할 것 같습니다.