백준 2110번 공유기 설치

문제

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

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

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

입력

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

출력

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

 

이분 탐색으로만 풀어야 하는 문제.. 좋은 문제인지는 모르겠다..

N개 정렬시킨 후에 가장 최소는 1 최대는 첫원소와 마지막원소의 차이

최소와 최대 사이에 정답으로 출력해야하는 값이 존재한다.

따라서 이분탐색으로 result를 변경시켜가면서 만약 조건에 부합하면 그 값을 키우고 부합하지 않으면 값을 줄이면서 진행.

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;


int N, C;
int arr[200000];

bool possible(int dist)

{

	int cnt = 1;

	int prev = arr[0];

	//조건 충족하는지 확인

	for (int i = 1; i < N; i++)

		if (arr[i] - prev >= dist)

		{
			
			cnt++;

			prev = arr[i];

		}



	//조건 충족

	if (cnt >= C)

		return true;

	return false;

}






int main(void)
{
	cin >> N >> C;
	for (int i = 0; i < N; i++)
	{
		long long x;
		cin >> x;
		arr[i] = x;
	}

	sort(arr, arr + N);
	int left = 1;
	int right = arr[N - 1] -arr[0];

	int result = 0;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (possible(mid))
		{
			result = max(result, mid);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}


	cout << result << endl;
}