BOJ 2110: 공유기 설치

#BOJ 2110: 공유기 설치

2110번: 공유기 설치

#풀이

진짜 막막했다. 사실 공유기가 고정되어 있으면 정말 쉽게 풀 수 있다고 생각이 들었는데 공유기의 개수가 변할 수 있어서 생각하기가 어려웠다.

 

맨 처음에는 2개의 집을 골라서 무조건 인접한 집의 최대 거리라 생각하고 공유기를 다 넣을 수 있는지 생각했는데

그게 아니었다.

인접한 집들의 거리를 이분탐색으로 찾아내면 비교적 간단하게 해결할 수 있다.

 

공유기가 있는 가장 인접한 거리에 있는 집의 최대 값(x)을 구해야 하므로 

공유기의 최소 거리가 x만큼은 떨어져 있어야 하는 것이다.

 

그래서 공유기를 집마다 x만큼 떨어져 가져도 공유기를 c개 만큼 다 가질 수 있는지 판단하면 해결할 수 있다.

 

내가 말을 이상하게 적어서.. 이해를 못할 수 도 있지만 

 

정리하면

공유기 끼리의 최소거리(x)를 이분탐색으로 찾는다.

매개 변수 탐색으로 x만큼 떨어져 공유기를 집마다 가지는데 총 공유기의 개수를 c랑 비교한다.

 

이렇게 해결하면 x를 구할 수 있다.

 

#코드

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

using namespace std;

int n, c;
vector<long long> arr;
bool func(int len) {
	int index = 0;
	int wifi = 0;
	while (index < n) {
		index = lower_bound(arr.begin(), arr.end(), arr[index] + len) - arr.begin();
		wifi++;
	}
	return wifi >= c;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	int st = 1;
	int en = 1000000000;
	while (st < en) {
		int mid = (st + en + 1) / 2;
		if (func(mid))
			st = mid;
		else
			en = mid - 1;
	}
	cout << st << '\n';
	return 0;
}