[C++] 2110: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

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

출력

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

풀이

이진 탐색 문제.

house[ ] 배열에는 각 집의 좌표가 오름차순 정렬되어 있다.

공유기의 최소 거리(1)과 최대 거리(첫 집과 끝 집 좌표의 차)를 first, last로 하여 이분 탐색을 실행한다.

mid가 현재 공유기 사이의 거리가 된다.
첫번째 집을 마지막 좌표로 시작하여, 마지막 좌표로부터 현재 공유기 사이의 거리보다 같거나 멀리 있는 집을 센다. 같거나 멀리 있는 집이 있다면, count를 1 늘리고, 마지막 좌표를 그 집으로 갱신한다. count가 c보다 작거나 같을 때까지 진행한다.

그 후, count가 c와 같다면, 해당 거리로는 공유기를 c 혹은 그 이상 설치할 수 있다는 뜻이므로, 조건을 만족한다. 따라서 result를 갱신한다. 해당 거리보다 더 긴 값이 조건을 충족할 수도 있으므로, first = mid + 1 하여 더 긴 값들을 탐색한다.

count가 c와 다르다면, c보다 count가 작다는 뜻이다. 즉 공유기를 c개보다 적게 설치할 수 있다는 뜻으로, 조건을 만족하지 않는다. 해당 거리보다 더 짧은 값을 더 탐색한다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

void input_data(void);
void find_max(void);

int n, c, result;
int house[200000];

int main(void)
{
	input_data();
	find_max();

	return (0);
}

void input_data(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> c;

	int i = -1;
	while (++i < n)
		cin >> house[i];

	sort(house, house + n);

	return ;
}

void find_max(void)
{
	int first = 0, last = house[n - 1] - house[0];

	while (first <= last)
	{
		int mid = (first + last) / 2;
		int count = 1, last_coordinate = house[0];
		int i = 0;

		while (++i < n && count < c)
		{
			if (house[i] - last_coordinate >= mid)
			{
				count++;
				last_coordinate = house[i];
			}
		}

		if (count == c)
		{
			result = mid;
			first = mid + 1;
		}
		else
			last = mid - 1;
	}

	cout << result << '\n';

	return ;
}

성공 !