[백준 알고리즘] 2110번 자바(Java) 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

풀이

각 공유기의 거리를 이진 탐색하는 방법을 생각했다이진탐색범위가 최소 0부터 최대 10억이고 이진탐색은 O(log x)을 가진다. 따라서 시간 복잡도는 O(log xi)가 된다 

 

다음 그림과 같은 과정을 거쳐서 공유기 3개 설치 가능한 최대 거리는 3이 된다

 

 

예제 입력 예시

5 3
1
2
8
4
9

 

예제 출력 예시

3

 

소스코드

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

//2110번 공유기 설치
public class P2110 {
    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[] homeX = new int[N];

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

        int len = homeX[N-1] - homeX[0];
        if(C == 2){  //공유기 2개인 경우
            System.out.println(len);
        }
        else{
            int curX = len/2;
            int standard = len/2;
            boolean pass = false;
            while(true){
                int count = 0;
                //이분탐색: 6 -> 3 -> 4 -> 차이 /2 = 0이면 1올려주기(if문) 그렇게 해서 false되면 before가 답
                int home = homeX[0];
                for (int i = 1; i <N; i++) {
                    if(homeX[i] - home >= curX){
                        count++;
                        home = homeX[i];
                    }
                }
                if(count >= C-1){ //거리 더 넓히기
                    if(standard /2 ==0) {
                        pass = true;
                        curX += +1;
                    }
                    else{
                        standard /= 2;
                        curX += standard;
                    }
                }
                else{ //거리 더 낮추기
                    if(pass){
                        curX--;
                        break;
                    }
                    else{
                        if(standard /2 ==0) {
                            curX -= 1;
                        }
                        else{
                            standard /= 2;
                            curX -= standard;
                        }
                    }
                }
            }
            System.out.println(curX);
        }
    }
}

 

 

 

 

문제 출처

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