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

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

2110번: 공유기 설치

 

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[] 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]; // 가능한 최대 거리
        int answer = 0;

        while(left<=right){
            int mid = (left+right) / 2; // 기준 간격
            int start = arr[0];

            int cnt = 1; // 공유기 개수
            for(int i=1; i<n; i++){ // 기준 간격으로 공유기 설치
                int gap = arr[i] - start;
                if(gap >= mid){
                    cnt++;
                    start = arr[i];
                }
            }
            if(cnt >= c){ // 설치해야할 공유기 개수보다 많이 설치함 -> 최대 거리 찾기 위해 거리를 늘림
                answer = mid;
                left = mid + 1;
            }else{ // 적게 설치함 -> 거리를 줄임
                right = mid - 1;
            }
        }
        System.out.println(answer);
    }
}

 

 

집의 좌표가 최대 10억이 될 수 있다. 이분탐색으로 풀어야 한다.

 

 

 

일단 가장 왼쪽 집부터 공유기를 설치해야 최대한 멀게 설치할 수 있다. 

 

 

가장 인접한 두 공유기 사이의 거리를 mid라고 하고 공유기를 설치해보자.

mid = 2 이면,

1, 4, 8 이렇게 3개를 설치할 수 있다 -> 가능

 

mid = 5 면,

1, 8 두개를 설치 할 수 있다.  -> 불가능 

 

mid = 3 이면,

1, 4, 8 이렇게 3개를 설치할 수 있다. -> 가능 

 

 

거리가 2일때와 3일 때 둘다 가능하지만, 우리가 구하고자 하는거는 최대 거리이므로 답은 3이 된다.

 

 

 

 

=> 공유기 사이 거리를 mid로 설정하고, mid를 기준으로 공유기를 설치한다.

공유기를 C개 이상 설치 할 수 있다면 mid를 늘려나가며 최댓값을 확인하고,

설치할 수 있는 공유기 개수가 C개 미만이면 mid를 줄여나간다.