[백준] 2110번 공유기 설치

문제 설명

https://www.acmicpc.net/problem/2110

문제 풀이

• 이분 탐색을 이용하여 풀이하였다.
• 이분 탐색의 원리는 다음과 같다.

  • instaill (int length)
  • 특정 최소거리 n이 있을때 설치할 수 있는 공유기 갯수는 m개로 정해진다.
    집 좌표 arr를 순회하며 이전에 (현재 좌표 - 직전 설치한 좌표) >= n일때 설치해주고
    직전 설치한 좌표를 갱신해주면 설치할 수 있는 공유기 갯수 m개를 구할 수 있다.
  • 위 함수를 기준으로 C값과 비교하여 이분탐색에서 어느쪽으로 이동할지를 판별할 수 있다.

소스 코드 (JAVA)

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

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N, C;
    public static int maxLength;
    public static int[] arr;

    public static int install(int length) {
        int prevInd = 0;
        int cnt = 1;
        for (int i = 1; i < N; i++) {
            //최소 거리 이상이면 설치
            if (arr[i] - arr[prevInd] >= length) {
                cnt++;
                prevInd = i;
            }
        }
        return cnt;
    }

    //이분 탐색
    //최소 거리를 탐색의 범위로 잡고 최소 거리일 때 설치 가능 갯수를 가지고 탐색
    public static int solve() {
        int lo = 0;
        int hi = maxLength + 1;
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (install(mid) < C) hi = mid;
            else lo = mid;
        }
        return lo;
    }

    //입력
    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(br.readLine());
        Arrays.sort(arr);
        maxLength = arr[N-1] - arr[0];
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}