백준 2110 공유기설치 c++ // 매개변수탐색, 이분탐색 hard

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

2110번: 공유기 설치

1. 의사코드

1. 첫번째 집을 선택하는게 최선인가? ㅇㅇ

귀류법 : 첫번째집을 선택안하는게 최선이라고 가정 ->

ex) 1 2 5  에서 2부터 2개선택(2,5) 하는경우 간격은 3 / (1,5)선택하는 경우 간격이4 -> 모순

- > 따라서 첫번쨰 집을 선택하는게 최적해를 보장한다.

 

2. 가장 중요한점은 st, en이 v의 값이 아닌 집간 최소거리, 최대거리를 의미한다는 점이다. 

mid : 현재 집 사이의 간격

 

3. st = 1 , en = 끝값-초기값(9-1==8), mid = 4

4. 현재mid로 간격설정시 공유기 갯수가 c미만임 -> 안됨 -> 간격을더 줄여야함 -> en(최대거리)를 줄이면됨.

됨 -> 간격을 늘려야함 -> st(최소거리)를 늘리면됨. 

5. 이때, 간격4가 안된다면, 그보다 큰간격 (5,6,7,8...)은 당연히 안되므로 -> 이분탐색으로 범위를 확 줄일수  있다.

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ret;
int n, c;
vector<ll> v;

//간격이 len 일때, 설치가능공유기가 c개이상인가?
//값차이가 len 이상이면, 설치하면 된다.
int go(ll len) {
	ll cnt = 1; //처음집에는 무조건 설치함
	ll cur = v[0];
	for (int i = 1; i < n; ++i) {
		if (v[i] - cur >= len) {
			cur = v[i];
			cnt++;
		}
	}
	return cnt >= c;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>>c;
	for(int i=0;i<n;++i){
		ll tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());
	//* 매개변수 탐색!
	//1. 가장 인접한 공유기사이 거리를x로설정
	//2. x기준으로 공유기 설치
	//3. 공유기를 c개이상 설치가능 -> 여유있음 & 정답후보임-> x를늘리고 재탐색
	//4. c개이상 설치불가 -> x를 줄이고 다시탐색

	ll st = 1; //집간 최소거리
	ll en = v[n - 1] - v[0]; //집간 최대거리
	ll mid; //현재 간격
	while (st <= en) {
		mid = (st + en) / 2;

		//간격을 mid로 했더니 공유기가 c개이상임 -> 정답후보 -> 더큰mid가 있는지 탐색 
		if (go(mid)) {
			st = mid + 1;
			ret = max(ret, mid);
		}
		//공유기가 c개 미만임 -> 불가 -> 간격을줄여야함
		else {
			en = mid-1;
		}
	}

	
	cout << ret;
	return 0;
}