백준 2110번 공유기 설치 C++

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

 

우선 입력받은 집의 위치들을 오름차순으로 정렬한다.

가능한 최소 간격은 1, 최대 간격은 제일 오른쪽 집-제일 왼쪽 집 이다.

left를 1, right를 house[n-1] - house[0] 으로 놓고 이분탐색을 하면서 답을 구할 수 있다.

설치한 공유기의 수가 C보다 크거나 같으면 간격을 넓혀야 하기 때문에 left를 mid+1로 바꾼 뒤 답을 갱신해주고,

설치한 공유기의 수가 C보다 작다면 간격을 좁혀야 하기 때문에 right를 mid-1로 바꾼다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, c;

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

	cin >> n >> c;
	vector<int> house(n);
	for (int i = 0; i < n; i++) {
		cin >> house[i];
	}
	sort(house.begin(), house.end());
	int left = 1;
	int right = house[n - 1] - house[0];
	int ans = -1;
	while (left <= right) {
		int mid = (left + right) / 2;
		int lastIndex = 0;
		int cnt = 1;
		for (int i = 1; i < n; i++) {
			if (house[i] - house[lastIndex] >= mid) {
				cnt++;
				lastIndex = i;
			}
		}
		if (cnt >= c) {
			ans = max(ans, mid);
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	cout << ans;
};