이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 70 번째 글 입니다.
목차
실버2 : 파라메트릭 서치 문제이다.
생각
파라메트릭 서치 문제이다. 일단 완전 탐색이 불가하고, 답을 제시했을 때 분기를 만들 수 있다는 점에서 바로 접근했다.
- 인접한 집간의 최대 거리를 제시한다.
- 제시한 거리를 보다 크거나 같은 곳에 공유기를 설치했을 때 몇개를 설치할 수 있는지를 반환한다.
- 그 반환한 값(즉 내가 제시한 거리로 공유기를 설치했을 때 대수)이 C와 어떤지 비교한다.
- C보다 작다면 거리를 너무 크게 잡았으므로 거리를 줄여서 제시한다.
- C보다 같거나 크다면 이 값은 후보가 될 수 있는 값이다. 후보인 이유는 지금 제시한 거리보다 큰 값에서 C와 같은 값이 나올 수 있기 때문에 더 탐색한다.
Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
int N, C;
int a[200000];
int f(int num){
int count = 1;
int before = 0;
for (int i = 1; i < N; i++) {
if (a[i]-a[before] >= num) {
count++;
before = i;
}
}
return count;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> C;
for (int i = 0; i < N; i++) cin >> a[i];
sort(a, a+N);
int start = 1, end = 1e9, ans = 0;
while (start <= end) {
int mid = (start+end)/2;
int count = f(mid);
if (count < C) {
end = mid - 1;
} else {
ans = max(ans, mid);
start = mid + 1;
}
}
cout << ans << '\n';
return 0;
}