백준 2110번 : 공유기 설치

 

 

 

문제를 보고 이해하는데 오래 걸리고, 힌트를 받았음에도 도통 모르겠어서 답을 찾아봤다.

많이 나온 답을 보고 해석한 내용이다.

 

 

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

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int c = Integer.parseInt(line[1]);
		
		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 start ,cnt, dist, ans = 0, mid = 0;
		int limit = right/c+1;
		
		while (left <= right) {
			mid = (left+right)/2;
			if(limit <= mid) 
				right=mid-1;
			start = arr[0];
			cnt = 1;
			
			for(int i=1;i<n;i++) {
				dist = arr[i]-start;
				if(mid<=dist) {
					++cnt;
					start= arr[i];
				}
			}
			if(cnt>=c) {
				ans =  mid;
				left = mid+1;
			} else {
				right=mid-1;
			}
		}
		System.out.println(ans);
	}
}

 

아래의 예시 : 공유기 3대의 최대 거리를 구한다.

 

 - mid : 공유기 간 최소거리

 - left , right : mid를 구하기 위해 사용하는 변수, 첫 기준은 양 끝 간의 지점이다.

 - start : 남아있는 배열의 첫 지점.

 

 

첫 번째 루프

1      4       6       8       11        13      24     28      35   

left : 1                                              

right : 35-1 = 34                              

mid = (left + rignt) /2  =  17              

↑                                                       ↑

start                                        길이가 17(mid)이 넘는 첫 지점.

 

=> 17이 공유기 간 최소거리라고 한다면, 총 공유기는 1과 24 자리인 2개밖에 되지 않으므로 FAIL

=> 공유기 간 최소거리를 줄여야하기 때문에, 다음에 쓸 right를 mid-1 = 16으로 지정해준다.

 

 

두 번째 루프

1      4       6       8       11        13      24     28      35 

left = 1                                                             

right = 16                                                          

mid = (left + rignt) /2  =  17/2  = 8

↑                                 ↑                                    

start                    길이가 8이 넘는 첫 지점

                                   ↑                   ↑                  

                            새로운 start     길이가 8이 넘는 두 번째 지점.           

                                                        ↑                  ↑

                                                   새로운 start     길이가 8이 넘는 세 번째 지점.

 

=> 8이 공유기 간 최소거리라고 한다면 1, 11, 24, 35 이므로 공유기를 3개 넘게 설치할 수 있으므로 이 중에 3자리만 선택하면 되기 때문에

성공이라고 볼 수 있다. ( 답은 10이 되겠다.)

=> 하지만, 구하고자 하는 건 최대거리이므로 최적을 구하기 위해 다시 반복하도록 한다.

=> mid를 높이기 위해, left를 변경하도록 한다. left = mid +1로 설정해준다.

 

세 번째 루프

left = 9

right = 16

mid = 25/2 = 12

1      4       6       8       11        13      24     28      35 

↑                                            ↑                        

start                        길이가 12가 넘는 첫 지점

                                              ↑       ↑                  

                                새로운 start    길이가 12가 넘는 두 번째 지점

                                                       ↑                   ↑  

                                               새로운 start    길이가 12가 넘는 세 번째 지점

=> 12가 공유기 간 최소거리라고 지정했다면, 1, 13,24,35으로 4개를 설치할 수 있다.

하지만 아까와는 달리 답은 11이 나오므로 조금 더 큰 결과를 반환할 수 있다.

 

 

이런 과정을 반복하면서 가장 적합한 답을 고른다.

 

 

 

답을 보고나서 해석을 했더니 이해는 가지만, 보자마자 어떻게 풀어야 할지 감이 오지 않았다.

 

일단,

1. 10억이 넘는 걸 보니 분할해서 풀어야 할 것 같다.

2. 끝과 끝은 넣으면 유리하다. (가장 먼 지점을 포함해야 하니까)

3. 지점 간 거리의 최대 거리는 (마지막 지점 - 첫 지점) / (공유기 개수) + 1이 최댓값이다.

4. 이분 탐색의 기준을 '거리'로 잡는다.