공유기 설치 (feat. 백준, 2110번)

공유기 설치
https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, C, start = 1, end = 0, mid, idx, count;
	int x[200000];
	cin >> N >> C;
	for (register int n = 0; n < N; ++n)
		cin >> x[n], end = max(end, x[n]);
	sort(x, x + N);
	while ((end - start) >= 0) {
		mid = (end + start) / 2;
		idx = 0;
		count = 1;
		for (register int i = 1; i < N; ++i)
			if (x[i] - x[idx] >= mid)
				idx = i, ++count;
		if (count >= C)
			start = mid + 1;
		else
			end = mid - 1;
	}
	cout << end;
	return 0;
}
// *&)*@*

저보다 더 자세하게 설명한 블로그가 있어 해당 블로그를 공유합니다.

[백준] 2110번 : 공유기 설치 - JAVA [자바]