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

2110번: 공유기 설치

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

vector<int> Houses;

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

	int N, C;
	cin >> N >> C;

	Houses.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int X;
		cin >> X;
		Houses.emplace_back(X);
	}

	sort(Houses.begin(), Houses.end());

	int Solution = 0;
	int Left = 0;
	int Right = Houses.back();
	while (Left <= Right)
	{
		int Mid = (Left + Right) / 2;
		int Count = 1;

		int Distance = 0;
		for (int i = 1; i < N; ++i)
		{
			Distance += Houses[i] - Houses[i - 1];

			if (Distance >= Mid)
			{
				Distance = 0;
				++Count;
			}
		}

		if (Count >= C)
		{
			Solution = Mid;
			Left = Mid + 1;
		}
		else
		{
			Right = Mid - 1;
		}
	}

	cout << Solution;
}

---

 

주어진 개수의 공유기를 일정 간격으로 모두 설치할 수 있으면서

해당 설치 간격이 가장 큰 값이 되도록 하는 문제입니다.

이분탐색 알고리즘을 사용해서 풀었습니다.