[백준] 2110 공유기 설치 / 이분 탐색 (C++)

구하는 값이 "간격"의 값이므로,
간격의 수치를 이분 탐색하는 방식으로 진행한다.

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, totalRouterCnt;
	cin >> n >> totalRouterCnt;
	vector<int> house(n);

	int l, r, mid, routerCnt = 0, lastRouter, maxDist = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> house[i];
	}
	sort(house.begin(), house.end());

	// 간격의 최소, 최대값
	l = 0;
	r = house[n - 1] - house[0];

	while (l<=r)
	{
		mid = (l + r)/ 2;
		// 첫 번째 집에 공유기를 둔다.
		lastRouter = 0;
		routerCnt = 1;

		// mid 값만큼 차이가 나는 곳에 공유기를 둔다.
		for (int i = 1; i < n; i++)
		{
			if (house[i] - house[lastRouter] >= mid)
			{
				lastRouter = i;
				routerCnt++;
			}
		}
		// 가능하다면 간격 늘려서 다시 해본다.
		if (routerCnt >= totalRouterCnt)
		{
			maxDist = mid;
			l = mid + 1;
		}
		// 다 못 놓는다면 간격을 줄여야 한다.
		else if (routerCnt < totalRouterCnt)
		{
			r = mid - 1;
		}	
	}
	cout << maxDist;
	return 0;
}