[백준] 2110 공유기 설치

백준2110링크

문제

• 집 N개가 수직선 위(x1, ..., xN)
• 공유기 C개를 설치
• 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치

입력

집의 개수 N (2 ≤ N ≤ 200,000), C (2 ≤ C ≤ N)
N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력

풀이

알고리즘참고링크

공유기를 설치할 수 있는 거리
최소 거리 low= 1
최대 거리 high= 마지막 집 - 첫번째 집

이분탐색을 하면서 mid=(low+high)/2의 값을 조정하면서 C개 이상의 공유기를 설치할 수 있는 거리 중 가장 최대값을 구하기

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, C;
vector<int> house;

//mid값으로 공유기를 C개 이상 설치할 수 있는지 확인
bool chk(int mid) {
	int cnt = 1;
	int prev = house[0];

	for (int i = 0; i < N; i++) {
		if (house[i] - prev >= mid) {
			cnt++;
			prev = house[i];
		}
	}
	if (cnt >= C) {
		return true;
	}
	return false;
}

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

	cin >> N >> C;
	int temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		house.push_back(temp);
	}

	sort(house.begin(), house.end()); //집 번호순서대로 오름차순 정렬

	int low = 1, high = house[N - 1] - house[0];
	int maxdistance = 0;

	while (low <= high) {
		int mid = (low + high) / 2;
		if (chk(mid)) {
			maxdistance = max(maxdistance, mid);
			low = mid + 1;

		}
		else {
			high = mid - 1;
		}
	}
	cout << maxdistance << "\n";
	return 0;
}