[Java] 백준 2110번 : 공유기 설치

1. 문제

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

2110번: 공유기 설치

 

 

2. 풀이과정

집의 좌표가 10억이므로, 전체를 둘러보면 시간초과가 발생하므로 이진탐색을 택했다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputs[] = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int C = Integer.parseInt(inputs[1]);
        int pos[] = new int[N];

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

        Arrays.sort(pos);
        int l = 0, r = pos[N-1];
        while(l<=r){
            int m = (l+r)/2;
            int pre = pos[0], cnt = 1;
            for(int i=1; i<N; i++){
                if(pos[i]-pre >= m){
                    cnt++;
                    pre = pos[i];
                }
            }

            if(cnt < C){r = m-1;}
            else{l = m+1;}
        }
        System.out.println(r);
    }
}

 

 

결과