[PS] 백준 2110번 공유기 설치

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

집 N개가 수직선 위에 존재하고, 그 좌표가 주어진다. 각 집에 공유기를 설치한다고 했을 때, 공유기간 거리의 최소의 최대치를 구하는 문제이다.

뒤집어서 생각해보자
공유기간 거리의 최소를 정하고, 설치가 가능한지를 O, X로 표시해보면...

1 2 3 4 5 6 7 8 9 10
o o o o o o o x x x

위처럼 나타날 것이고, 구하고자 하는 문제의 정답은 바로 o와 x가 만나는 경계에서 가장 가까운 o가 위치한 7이다. 따라서, 공유기간 거리의 최소를 파라미터로 해서 이분탐색을 수행하면된다. 설치가 가능한지 불가능한지를 반환하는 함수를 정의하면 되고, 본 문제의 경우에는 이분탐색 종료시 left와 right 인덱스 중에서 right를 return하면 되겠다. (left가 오른쪽영역, 즉 x 영역으로 넘어가기 때문이다 반대로, 가능여부가 xxxxxxooooo의 형태로 나타난다면 left를 반환하면 될 것이다. 아마도...) 그리고 이와 같은 탐색을 parametric search 라고 한다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n, c;
int houses[200000];

bool check(int dist) {
	int cnt = 1;
	int prevPos = houses[0];
	for (int i = 1; i < n; i++) {
		if (houses[i] - prevPos >= dist) {
			prevPos = houses[i];
			cnt++;
		}
	}

	if (cnt >= c)
		return true;

	return false;
}

int paramSearch() {
	sort(houses, houses + n);

	int left = 0;
	int right = houses[n - 1];

	while (left <= right) {
		int mid = (left + right) / 2;
		
		bool isPossible = check(mid);
		if (isPossible) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	return right;
}

int main()
{
	cin >> n >> c;
	
	for (int i = 0; i < n; i++) {
		cin >> houses[i];
	}

	cout << paramSearch();
}