[BOJ] 2110 : 공유기 설치

풀이

이문제도 k번째수와 같이 이분탐색 문제란것을 떠올리지 못하면 막막하다.

최대거리를 임의값으로 설정해두고 첫째 좌표에서 임의값거리만큼씩 증가시켜보면서 개수를 센다. 그래서 C개 이상이 나오면 정답을 임시저장해두고 왼쪽거리를 늘린다. C개 미만이 나오면 오른쪽거리를 좁힌다.

참고할 부분은 항상 c개 이상이나오면 c개가 최적해이고, 첫째(arr[0])좌표에서 시작하는게 최대거리이란 점이다.

코드

이분탐색(파라메트릭 서치)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

long long arr[200001];

int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, c;
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	//오름차순 정렬
	sort(arr, arr + n);
	//최대거리를 이분탐색으로 찾는다
	int result = -1;
	int left = 1;
	int right = arr[n - 1] - arr[0];
	int now = (left + right) / 2;
	while (left <= right) {
		int flag = 0;
		int cnt = 1;
		int start = arr[0];
		for (int j = 1; j <= n - 1; j++) {
			if (arr[j] >= start + now) {
				start = arr[j];
				cnt++;
			}
		}
		if (cnt >= c) {
			result = now;
			flag = 1;
		}
		if (flag) {
			//답을 찾은경우 탐색 거리를 늘린다
			left = now+1;
		}
		else {
			//답을 못찾은 경우 탐색 거리를 좁힌다
			right = now-1;
		}
		now = (left + right) / 2;
	}

	cout << result;
	return 0;
}

Written on June 1, 2021