백준 2110 : 공유기 설치

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

1. 접근

• 거리의 범위는 1~(처음집과 끝집의 거리) 이다.
• 빠르게 정답 거리를 찾아내기 위해 이진탐색을 사용한다.
• 첫 집을 고정시켰을 때 대부분의 경우 답을 찾아낼 수 있다.
  (참고 : https://www.acmicpc.net/board/view/50802)
• 첫 집과 i번째 집과의 거리가 mid와 일치하면, i번째 집과 그 다음 집과의 거리로 넘어간다

2. 나의 풀이

#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;

int main() {
	int n, c;
	cin >> n >> c;
	int house[MAX];

	for (int i = 0; i < n; i++) {
		cin >> house[i];
	}
	sort(house, house + n);

	int start=1, end=(house[n-1]-house[0]), mid;
	int ret = 0; //최소거리의 최댓값

	while (start <= end) {
		mid = (start + end) / 2;
			
		int prev = house[0];
		int tem = 1;
		for (int i = 1; i < n; i++) {
			if (house[i] - prev >= mid) {
				tem++;
				prev = house[i];
			}
		}

		if (tem >= c) {
			ret = max(ret, mid);
			start = mid + 1;
		}
		else end = mid - 1;
	}

	cout << ret << "\n";
	return 0;
}

3. 참고

https://mygumi.tistory.com/301

http://melonicedlatte.com/algorithm/2018/07/29/132129.html