[백준]2110번 공유기 설치 - C++

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

2110번: 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

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

---

     

    집들의 좌표가 기준이 아닌 두 공유기 사이의 거리를 기준으로 이분 탐색을 진행하여 푸는 문제이다. 거리 len을 기준으로 집들의 배열을 순회하며 이전 집들과의 거리가 len 보다 길어졌을 때 cnt를 증가시킨다. 만약 cnt 가 C보다 크거나 같다면 공유기를 정답보다 같거나 많게 설치했다는 것으로 공유기 숫자를 줄이면 최소거리가 증가할 수 있다. 또한, 이는 더 많은 공유기의 숫자로도 최소 len거리 씩은 띄울 수 있다는 것이므로 정답(result)과 비교하여 그 길이가 더 길다면 저장해둔다. cnt 가 C보다 작다면 거리가 너무 커 정답보다 적게 설치했다는 것으로 최소 거리를 늘려 기준 공유기 숫자를 넘겨야 한다. 처음 len 은 작은 값( 1 )과 큰 값( 전체 집 사이의 최대 길이)의 반으로 두고 len을 증가시키려면 작은 값을 len+1로 감소시키려면 큰 값을 len-1으로 변경하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;
int N, C;
int arr[200'000];
int main() {
	cin >> N >> C;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);
	
	int s = 1;
	int e = arr[N - 1] - arr[0];
	int result = 0;
	while (s <= e) {
		int len = (s + e) / 2;
		int cnt = 1;
		int prev = arr[0];
		for (int i = 0; i < N; i++) {
			if (arr[i] - prev >= len) {
				cnt++;
				prev = arr[i];
			}
		}
		if (cnt >= C) {
			result = max(result, len);
			s = len + 1;
		}
		else e = len - 1;
	}
	cout << result;
	return 0;
}

---

    문제를 처음 풀때는 시작 점과 끝점은 포함하고 중간 지점을 구해 그 점과 가까운 집을 upper_bound를 활용하여 구한 다음 재귀를 활용하여 문제를 풀려고 구상하였다. 하지만 이는 짝수개의 집이 나왔을 때 어느 지점을 선택해야 할지 모호했다. 짝수개가 나오면 재귀로 푸는 것은 무리 일 것 같아 다른 방법을 생각했지만 생각이 나지 않았다. 그래서 구글링을 해보니 그 길이를 기준으로 이분 탐색을 하여 기준 길이를 늘렸다가 줄였다가 하며 최적의 길이를 찾는 것이었다. 생각해보니 답이 집들의 좌표가 아닌 최소 길이를 요구했으니 납득이 가능한 생각의 흐름이었다. 이분 탐색을 많이 풀지 않다 보니 어느 것을 이분 탐색할지 눈에 잘 안 보이는 문제들이 많은 것 같다. 더 많은 문제들을 풀어 이분 탐색에 더 익숙해져야겠다!