[백준] 2110. 공유기 설치 + 복습(이분탐색 정리)

문제

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

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

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

입력

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

출력

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

 

 

#include<bits/stdc++.h>

using namespace std;

vector<int>arr;
int cal(int d) {
	int c = 1;
	int idx = 0;
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] - arr[idx] >= d) {
			c++;
			idx = i;
		}
	}
	return c;
}
int main() {
	int n, m, x, ans = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x;
		arr.push_back(x);
	}
	sort(arr.begin(), arr.end());
	int le = 1, ri = arr.back() - arr.front();
	int mid = ri / (m - 1);

	while (1) {
		if (le > ri) {
			break;
		}
		int num = cal(mid);
		if (num >= m) {
			ans = mid;
			le = mid + 1;
			mid = (le + ri) / 2;
		}
		if (num < m) {
			ri = mid - 1;
			mid = (le + ri) / 2;
		}
	}
	cout << ans;
}

골드 5 이진탐색 문제입니다.

이진탐색 문제는 무엇을 기준으로 분류할지를 정하는 것이 중요합니다.

이 문제에서는 공유기를 나누어 설치하는 간격의 최솟값을 정해야 하므로, 설치가능한 간격을 기준으로 분류해야 합니다.

 

left=1 (최소 간격), right=arr.back()-arr.first()(최대간격)

n개의 마을에 c개의 공유기를 설치할 때, 간격의 최댓값은 (right)/(c-1)이므로 mid를 (left+right)/2가 아니라 right/(m-1)로 초기화 해주었습니다. right/(c-1)<=answer<=(left+right)/2 이기 때문입니다.

 

간격 mid로 설치할 수 있는 공유기의 갯수가 m보다 많거나 같으면 간격을 늘려 갯수를 줄이고,

m보다 작으면 간격을 줄여 갯수를 늘립니다.

 

============================================================================================

 

이분탐색 문제... 깨달은 부분

 

"어느 조건을 만족하는 최소 K를 구하라" 라는게 이분탐색의 문제입니다.

이 문제를 보면

 

"C개의 공유기를 N개의 집에 설치할때 가장 인접한 집사이의 최단 거리 K를 구하라"

에서 조건은 "C개의 공유기를 N개의 집에 설치할때" 이고, 구하는 것은 "가장 인접한 집사이의 최단거리 K" 입니다.

 

따라서 이분탐색문제임을 파악할 수 있습니다.

 

그래서 어떻게 풀어야 하느냐?

 

가장 인접한 집사이의 최단거리가 K라고 할때..... P개의 공유기를 N개의 집에 몇개 설치할 수 있는지 살펴보면 됩니다.

P개의 공유기가 C개 이상인경우, 답이될 수 있습니다.... 하지만 K보다 조금더 짧아도 답이 될 수 있으므로 조금더 살펴볼 필요가 있습니다.

ANSWER에 K를 저장해놓고,, 범위를 좀더 좁히면 됩니다.

 

따라서 이분탐색 문제는 Check(int K)라는 함수가 필요합니다. K에 대해 조건을 만족하는지, 그에대해 범위를 넓히던 줄이던 결정해야 합니다.

 

이분탐색 입니다.