06.06. 공유기 설치 [Binary Search & Parametric Search][백준 2110]

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

2110번: 공유기 설치

 

Algorithm classification : Binary Search, Parametric Search

 

06.06.1. Problem

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

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

 

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

 

06.06.2. Input limit

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

 

06.06.3. Output

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

 

06.06.4. Solution

이 카테고리의 문제 중에 골드라니! 상당히 반갑네요. 아마 Greedy가 조오금 섞여서 그런게 아닌가 싶습니다. 좌표에 따라 정렬을 하고 두 공유기 사이의 가능한 최대 거리가 구하고자 하는 값이니 이를 이분 탐색으로 찾으면 됩니다. 그리고 각 탐색에서 거리가 가능한지 Greedy하게 판별하면 되겠군요. Greedy에 대한 개념을 알고 싶은 분들은 아래의 link를 참고하시면 좋을 것 같습니다.(알고리즘 PS 카테고리에 Greedy 문제 풀이도 있으니 이를 참고하시면 금상첨화겠군요.)

2021.11.18 - [학부공부/Algorithm_알고리즘] - 05. Greedy Algorithm(1)

05. Greedy Algorithm(1)

2021.11.18 - [학부공부/Algorithm_알고리즘] - 06. Greedy Algorithm(2)

06. Greedy Algorithm(2)

 

계속 이어서 이야기 해보자면 결국 공유기를 많이 설치해야 하므로 가능한 한쪽으로 몰쳐서(?) 설치하는 것이 좋습니다. 이렇게 하여 C개 공유기를 모두 설치할 수 있으면 가능합니다. 집의 위치를 모두 탐색해야하기 때문에 O(N)의 시간복잡도가 필요하겠네요.

	int n, c;
	scanf("%d %d", &n, &c);
	int a[n], i, left = 0, right = 1000000000, mid, result, sum, start, temp;
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	
	
	while(left <= right){
		mid = (left + right) / 2;
		temp = 1;
		start = a[0];
		
		for(i = 1; i < n; i++){
			if(a[i] - start <= mid){
				continue;
			}
			else{
				start = a[i];
				temp++;
			}
		}
		//printf("%d %d %d > %d\n", left, right, mid, temp);
		if(temp < c){
			result = mid;
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	
	printf("%d", result);

 

생각보다 이 질문은 백준 online judge에 질문이 많았습니다. Test case는 질문 게시판에서 더 구하실 수 있을 겁니다. 어느 분이 N, C size가 200000 200000이나 되는 test case도 올려주셨더군요.

 

4 3
11
13
16
18
>> 2

3 3
1
3
4
>> 1

5 3
1
7
8
9
10
>> 3

2 2
6
5
>> 1

4 3
999999985
999999991
999999996
1000000000
>> 6