백준2110 공유기 설치

작성일 | In

문제 링크

  • http://icpc.me/2110

사용 알고리즘

  • parametric search

시간복잡도

  • O(N log 1e9)

풀이

좌표가 최대 10억까지 주어지므로 파라메트릭을 생각해봅시다.
공유기 사이의 거리를 m 이상으로 할 수 있는지는 O(N)만에 판단할 수 있습니다.
그렇다면 l을 0, r을 1e9로 설정해주고 이진 탐색을 하면 O(N log 1e9)만에 구할 수 있습니다.

거리를 m 이상으로 유지할 수 있는지 판단하는 함수는 그리디하게 구현하면 됩니다. 자세한 구현은 아래 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int n, c;

bool chk(int m){
	int cnt = 0;
	int prv = -1e9;
	for(int i=0; i<n; i++){
		if(prv + m <= v[i]){
			cnt++;
			prv = v[i];
		}
	}
	return cnt >= c;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> c;
	v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];
	sort(v.begin(), v.end());

	int l = 0, r = 1e9+7;
	for(int i=0; i<100; i++){
		int m = l + r >> 1;
		if(chk(m)) l = m;
		else r = m;
	}
	cout << l;
}