[백준] 2110: 공유기 설치 - JAVA

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

풀이

공유기를 C개 설치하면서 가장 인접한 두 공유기 사이의 거리를 최대ㅐ로 하는 문제이다.

공유기 사이의 거리를 기준으로 이분탐색을하여 풀었다.

이분탐색을 해야하므로 입력을 받아 배열을 정렬했다.

left와 right를 놓고 mid를 공유기 사이의 거리로 하여 그 거리만큼 띄웠을 때 몇개의 공유기를 설치할 수 있는지 판단했다.

설치가능한 공유기의 개수가 c보다 작다면 right를 mid로 줄이고

그렇지 않다면 left를 mid+1 로 증가시켰다.


메모리: 28912KB

시간: 312ms

언어: Java 11

코드

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

public class Main {
    static int[] arr;

    public static void main(String[] args) throws Exception {
        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());

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

        int left = 1;
        int right = arr[n - 1] - arr[0] + 1;
        while (left < right) {
            int mid = (left + right) / 2;

            int cnt = installWifi(mid);
            if (cnt < c) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(left - 1);
    }

    private static int installWifi(int n) {
        int cnt = 1;

        int pos = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int dist = arr[i] - pos;
            if (dist >= n) {
                cnt++;
                pos = arr[i];
            }
        }

        return cnt;
    }

}