백준 2110 - 공유기 설치

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

int N, C;
int k;
vector<int> arr;

int main() {
	cin >> N;
	cin >> k;
	long int before;
	long int totalDst = 0;

	long int point;
	cin >> point;
	arr.push_back(point);
	for (int i = 1; i < N; i++) {
		long int point2;
		cin >> point2;

		totalDst += point2 - arr[i - 1];
		arr.push_back(point2);
	}
	sort(arr.begin(), arr.end());

	int answer = 0;
	// 공유기간의 거리 최솟 값
	int start = 1;
	// 공유기간의 거리 최댓값
	int end = arr[arr.size() - 1] - arr[0];

	while (start <= end) {
		// 설치한 공유기 갯수의 최대 거리를 찾기
		int mid = (start + end) / 2;

		int previousHousePos = arr[0];
		// 맨 처음 집지점에 공유기 설치
		int installCount = 1;
		// 집들을 순차적으로 검색
		for (int i = 1; i < arr.size(); i++) {
			if (arr[i] - previousHousePos >= mid) {
				installCount++;
				previousHousePos = arr[i];
			}
		}

		// 설치된 공유기 갯수가 계획 된 공유기 설치 갯수보다 많으면
		// 탐색 범위를 높임
		if (installCount >= k) {
			start = mid + 1;
			// 설치된 공유기 갯수가 기존 계획 보다 많다 == 현재 공유기 간의 최대 거리가 답보다 작거나 같다
			answer = max(answer, mid);
		}
		// 설치된 공유기 갯수가 계획 된 공유기 설치 갯수보다 낮으면
		// 탐색 범위를 좁힘
		else {
			end = mid - 1;
		}
	}
	cout << answer;
	return 0;
}