[백준]Baekjoon2110(이진탐색)

문제링크 : https://www.acmicpc.net/problem/2110

문제를 풀기 위해서 먼저 sort함수를 이용하여 입력받은 집의 좌표를 오름차순으로 정렬한다.

다음으로 left = 1 , right = 맨 뒤의 좌표 - 맨 앞의 좌표

로 하여 이진탐색을 수행한다.

특정 거리에 이르기 까지는 원하는 수의 공유기를 충분히 놓을 수 있지만

그 특정 거리에서 하나라도 커지는 순간 원하는 숫자의 공유기를 놓지 못한다는 점을 이용한다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, C;
long long house[200000];
bool gap(long long num)
{
	int start = 0;
	int cnt = 1;
	for (int i = 1; i < N; i++)
	{
		if (house[i] - house[start] >= num) {
			start = i;
			cnt++;
		}
	}
	return cnt >= C;
}

int main()
{
	scanf("%d %d", &N, &C);
	for (int i = 0; i < N; i++) scanf("%lld", &house[i]);
	sort(house, house + N);
	long long left = 1;
	long long right = house[N - 1] - house[0];
	long long result = 0;
	while (left <= right)
	{
		long long mid = (left + right) / 2;
		if (gap(mid)) {
			if (mid > result) result = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	printf("%lld\n", result);
}