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

공유기 설치

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	18137	7233	5325	42.295%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
5 3
1
2
8
4
9

예제 출력 1 복사

xxxxxxxxxx
3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

 

 

풀이

 

이분탐색을 이용해서 풀었습니다.

 

이분탐색의 mid값은 두 공유기 사이의 거리로 가정하고 풀면 됐습니다.

 

가장 인접한 두 공유기 사이의 최대 거리를 구하려면 어떻게 해야 할 까 고민을 되게 많이 했었는데

어찌 됐건 "가장 인접한 두 공유기 사이의 최대거리" 이것은 미리 두 공유기 사이의 거리를 정해놓고 풀면서 해결하면 됐습니다.

 

위에서도 말했듯, 이분탐색을 이용 할 때 mid값은 두 공유기 사이의 거리로 가정하고 풀었습니다.

        String [] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        c = Integer.parseInt(input[1]);
        
        
        for(int i=0; i<n; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);
        
        
        int start = 1;
        int end = list.get(n-1)-list.get(0);
        

 

보면 start와 end값이 이분탐색을 시작하는 기준입니다.

start가 0이 아니라 1인 이유는 두 공유기 사이의 거리가 0일 순 없으니 최솟값인 1로 가정하고 푸는 것 입니다.

 

end를 볼까요 list.get(n-1) - list.get(0)을 하고있네요.

위에서 정렬을 했으니 즉 주어진 집의 좌표에서 가장 가까운집과 가장 먼 집을 빼고있습니다.

 

생각을 다르게 해볼까요, 1에 있는 점과 100에 있는 점 사이의 최대거리는 몇일까요?

99입니다.

 

즉 이분탐색을 할 때 mid값은 두 공유기 사이의 거리로 하기로 했으니 start에는 가장 짧은 거리,

end에는 가장 긴 거리를 둬야 합니다.

 

그래서 end에는 list.get(n-1) - list.get(0)을 두었습니다.

 

그 다음 이분탐색 관련된 부분을 보겠습니다.

x
        while(start<= end) {
            int mid = (start+end)/2;
            int cnt = 1;
            
            int tmp = list.get(0)+mid;
            
            for(int i=0; i<n; i++) {
                if(list.get(i)>=tmp) {
                    cnt++;
                    tmp = list.get(i)+mid;
                }
            }
            
            
            if(cnt >= c) {
                ans = mid;
                start = mid+1;
            }
            else {
                end = mid-1;
            }
            
        }

 

cnt에 대해서 이해가 잘 안될수 있는데 cnt는 설치한 공유기의 개수입니다.

지금 이게 무슨소리지 하고 이해가 잘 안되실수 있는데, 저희는 이분탐색의 mid값을 두 공유기 사이의 거리로 두었고

 

mid값을 기준으로 나누었을때 공유기를 몇개 설치할까 라는 기준입니다.

cnt가 1부터 시작하는건, 첫번째 집에 공유기를 설치하기 때문에 1로 두었습니다.

 

int tmp = list.get(0)+mid; 이 부분을 볼까요

첫번째집 + mid한 값 입니다.

 

즉 첫번째 집이 1에 있고 현재 저희가 정한 mid값이 5라면

다음 공유기가 설치될 장소는 6 이상에 있는 집입니다.

 

그 부분을

            for(int i=0; i<n; i++) {
                if(list.get(i)>=tmp) {
                    cnt++;
                    tmp = list.get(i)+mid;
                }
            }

이렇게 순회를 하면서 i번째 집의 좌표가 그 전에 공유기를 설치한 위치 + 공유기의 길이 (mid)와 크거나 같으면

그쪽에다가 공유기를 설치했다고 치는 것입니다.

 

예를들어서 1, 4, 6 , 11 이렇게 집이 있다고 볼까요

 

mid값은 5라고 하겠습니다.

 

그럼 첫번째 집에서 공유기를 하나 설치하면 1+5 = 6 이 됩니다.

즉 다음 공유기를 설치할 위치는 6 좌표에 있는 것이고

 

반복문을 순회하면서

1,4,6,11

 

1 -> 설치

4 -> 6보다 작으니 설치 X

6 - > 설치 이 때 6에서 5의 길이의 공유기를 설치했으니 다음 설치할 위치는 11입니다

11 -> 설치

 

이런 메커니즘으로 흘러간다고 생각하시면 됩니다.

 

그래서 저희가 가정한 mid의 길이로 공유기를 설치 했을때 주어진 공유기의 개수 c보다 크다면

 

공유기를 더 적게 설치해야 하니 mid값을 늘려주면 됩니다.