[C++ 백준 문제풀이] 공유기 설치

 

 

[ 문제 이해 ]

 

집의 좌표가 n 개 만큼 입력된다.

공유기의 개수가 입력된다.

 

가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치한다.

 

 

[ 문제 전략 ]

 

공유기 사이의 최소 거리를 설정 한 다음, 그 거리를 조정 해 나가면서

 

조건에 맞는 거리의 최대값을 구하기로 했다.

 

그러려면 이분 탐색으로 시작점을 첫 번째 집, 마지막 점을 집의 마지막 좌표로 설정했다.

 

조건에 맞는 거리의 최대값이라고 하면 이해하기 어려운데,

 

총 공유기의 개수 만큼 공유기를 설치 했다면 조건에 맞는 거리가 되는 것이고

 

조건에 맞는 거리 중, 우리는 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치해야 하므로

 

최대값을 구하려는 의도이다.

 

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

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

	int n, c;
	std::cin >> n >> c;

	std::vector<long long> h(n, 0);

	for (int i{ 0 }; i < n; i++) {
		std::cin >> h[i];
	}

	std::sort(h.begin(), h.end());

	if (c == 2) {
		std::cout << h[n - 1] - h[0] << "\n";
		return 0;
	}

	int e = h[n-1];

	int s = 0, mid;
	int ans = 0;
	while (s < e) {
		mid = (s + e) / 2;

		int k = 1;
		long long b = h[0];
		int cnt = 1;
		while (k < n && cnt < c) {
			if (h[k] - b >= mid) {
				cnt++;
				b = h[k];
			}
			k++;
		}

		if (cnt < c) {
			e = mid;
		}
		else {
			ans = std::max(ans, mid);
			s = mid + 1;
		}
	}

	std::cout << ans << "\n";
}