Boj 2110) 공유기 설치

문제

백준 2110

설명

전략은 공유기 간의 최소거리를 인자로 하는 Paramteric Binary Search 를 하는 것이다.

이때 그리디적인 전략이 필요한데, 바로 무조건 처음 집에 공유기를 설치하는 것이 답 중에 하나라는 것이다.

• 처음 집에 공유기가 없는 임의의 배치에서 가장 왼쪽 공유기를 처음 집으로 옮기면 거리가 더 커지게 된다. 이는 왼쪽에서 더 가까워질 공유기가 없기 때문이다. 그러므로 만약 임의의 배치가 답이었다면 수정한 배치 역시 답이 된다.

이를 바탕으로 처음 집부터 최소거리를 넘는 집을 세주어 Parameteric Binary Serach 를 된다.

시간 복잡도

O(N * Log(범위))

코드

int n, m;
int arr[200001];

int Count(int l)
{
	int cnt = 1, cur = arr[0];

	for (int i = 1; i < n; i++)
	{
		if (arr[i] - cur < l) continue;
		cur = arr[i];
		cnt++;
	}
	
	return cnt;
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr + n);
	
	int start = 1, end = arr[n - 1] - arr[0], mid;
	int ans = 1;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (Count(mid) >= m) {
			ans = mid;
			start = mid + 1;
		}
		else end = mid - 1;
	}
	
	cout << ans;
}