백준 2110번, 공유기 설치 풀이

문제

백준 2110번

풀이

서로의 간격을 $ mid $ 이내로 C개의 공유기를 모두 배정할 수 있는가?

 

라는 결정 문제로 두었을 때, NNN...YYY로 단조롭게 나올테니 파라메트릭 서치를 사용할 수 있습니다.

 

발상과 구현에서 살짝 어렵다고 생각합니다. 실버 1~2 문제는 아니라고 생각합니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	ll n, c;
	cin >> n >> c;
	set<ll> s;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		s.insert(a);
	}

	ll l = 0, r = 1e9;
	for (int i = 0; i < 35; i++) {
		ll mid = (l + r) >> 1;
		ll pos = *(s.begin()), f = 0;

		for (int i = 1; i < c; i++) {
			auto it = s.lower_bound(pos + mid);
			if (it == s.end()) {
				f = 1;
				break;
			}

			pos = *it;
		}

		if (f) r = mid;
		else l = mid + 1;
	}

	cout << ((l + r) >> 1) - 1;
}