[BOJ/C++] 2110 공유기 설치 : 이분 탐색

문제

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

풀이

어떻게 해야하는지 접근 자체도 감이 안왔고, 풀이 보고도 한참을 이해못했다ㅠ 이분 탐색에 취약한 것 같다... 당분간 이분 탐색 조져야겠다 ‼️

접근)

• 입력이 10억 ➡️이분 탐색
• 집들 사이의 거리로 이분 탐색 진행
• 가장 인접한 두 공유기 사이의 거리를 최대로 해라
  결국은, 모든 공유기들의 간격이 공평하도록 설치하면 됨

풀이)

1. 이분 탐색을 위해 정렬

2. start(공유기를 설치할 수 있는 최소 거리), end(공유기를 설치할 수 있는 최대 거리), mid(공유기를 가장 공평하게 설치할 수 있는 간격) 초기화

3. 첫 번째 집에 공유기를 설치한 뒤, 나머지 집들 간의 간격을 확인하며 mid 이상으로 떨어져 있는 집 탐색
   3-1. 첫 번째 집으로부터 mid 이상 떨어져 있는 집을 찾은 경우, 해당 집에 공유기를 설치하고, 해당 집 기준으로 다시 mid만큼 떨어져있는 집 탐색

4. 모든 집을 탐색했다면, 이분 탐색을 이용해 공유기 설치 간격 조정
   4-1. 설치한 공유기 개수가 C개 미만➡️공유기 더 설치해서 간격 줄일 수 있음
   4-2. 설치한 공유기 개수가 C개 이상➡️더 큰 간격으로 갱신
   

코드

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

using namespace std;

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

	int N, C;
	int ans = 0;
	vector<int> pos;

	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		pos.push_back(tmp);
	}
	sort(pos.begin(), pos.end());
	
	int start = 1; //최소 거리
	int end = pos[N - 1] - pos[0]; //최대 거리

	while (start <= end) {
		int wifi = 1;
		int mid = (start + end) / 2;
		int st = pos[0];

		for (int i = 1; i < N; i++) {
			if (pos[i] - st >= mid) {
				wifi++;
				st = pos[i];
			}
		}

		if (wifi >= C) {
			ans = max(ans, mid);
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}

	cout << ans;

	return 0;
}