백준] 2110 - 공유기 설치

시간 제한 : 2초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	int n, c, start = 1, mid, end, cnt = 0, ans = 1;
	cin >> n >> c;
	vector<int> coord(n);
	for (int i = 0; i < n; i++)
		cin >> coord[i];

	sort(coord.begin(), coord.end());
	end = coord[n - 1] - coord[0];
	while (1)
	{
		mid = (start + end) / 2;
		cnt = 1;
		for (int i = 0; i < n-1; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (coord[i] + mid > coord[j])
					continue;
				else
				{
					i = j - 1;
					cnt++;
					break;
				}
			}
		}
		if (start > end)
			break;
		if (cnt >= c)
			ans = mid, start = mid + 1;
		else
			end = mid - 1;
	}
	cout << ans;
}

Tip

이분 탐색으로 분류되어 있는데, 공유기를 가장 멀리 배치할 수 있는 거리를 이분 탐색하는 것으로 결과가 답이 된다.