문제

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

풀이

N개의 집 중에서 공유기를 설치할 집 C개를 선택하여, 그 중에서 가장 인접한 두 공유기 사이의 최대 거리를 구해보려고 했다. 그런데, 이렇게 N개 중에 C개를 선택하는 조합으로 모든 경우의 수를 구하면, N의 최대 크기가 20만이기 때문에 시간초과가 날 수밖에 없다.

이처럼 최적화 문제를 완탐으로 풀기 어려울 때 생각해볼 수 있는 알고리즘 중 하나가 파라메트릭 서치이다. 즉, 최적화 문제를 결정 문제로 바꾸고 이분 탐색으로 해를 구하는 것이다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll; 

const int MAX = 200001; 
int houses[MAX];
int N, C; 

// 공유기 간의 거리가 x일 때, 
// 설치 가능한 공유기가 C개 이상인가? 
bool decision(ll x){
	ll prev = houses[0]; 
	int cnt = 1;  
	
	for(int i = 1; i < N; i++){
		// 이전 집과의 거리가 x 이상이면 
		if(houses[i] - prev >= x){
			// 현재 위치에 공유기 설치 
			cnt++; 
			prev = houses[i]; 
		}
	}

	return cnt >= C; 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> C; 

	for(int i = 0; i < N; i++){
		cin >> houses[i]; 
	}

	sort(houses, houses + N);

	ll left = 1;
	ll right = houses[N - 1] - houses[0];
	ll ans = 0; 

	while(left <= right){
		ll mid = (left + right) / 2; 

		if(decision(mid)){
			ans = max(ans, mid); 
			left = mid + 1; 
		}else{
			right = mid - 1; 
		}
	}

	cout << ans; 

	return 0; 
}