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

-문제

 

 

-코드

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

vector<int> a;

int calcul(int n)
{
	int cnt = 1;
	int pos = a[0];
	
	for (int i = 1; i < a.size(); i++)
	{
		if (a[i] - pos >= n)
		{
			cnt++;
			pos = a[i];
		}
	}
	return cnt;
}

int main()
{
	int n, m, tmp, res = 0;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &tmp);
		a.push_back(tmp);
	}
	
	sort(a.begin(), a.end());

	int rt = a[n-1], lt = 1, mid;

	while (lt <= rt)
	{
		mid = (rt + lt) / 2;
		if (calcul(mid) >= m)
		{
			lt = mid + 1;
			res = mid;
		}
		else
		{
			rt = mid - 1;
		}
	}

	printf("%d", res);
	return 0;
}