[백준] 2110번: 공유기 설치

문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제 해결

이분탐색

 

결과

 

코드

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

using ll = long long;
const int LM = 200005;
int n, c;
ll pos[LM];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> c;
	for (int i = 0; i < n; i++)
	{
		cin >> pos[i];
	}

	sort(pos, pos + n);

	ll low = 0, high = pos[n - 1];
	ll ans = 0;
	while (low <= high)
	{
		ll mid = (low + high) / 2;
		ll cnt = 1;
		ll last = pos[0];
		for (int i = 1; i < n; i++)
		{
			if (pos[i] - last >= mid)
			{
				cnt++;
				last = pos[i];
			}
		}

		if (cnt >= c)
		{
			ans = mid;
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	cout << ans;
	return 0;
}