백준 2110번: 공유기 설치
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
이 문제는 처음에 볼 때 이분탐색으로 푸는 것임을 알고 있음에도 고민을 많이 하였고 이분탐색이라도 기준을 어떻게 잡아야할지 감이 안잡혔다. 그래서 살짝힌트를 보았고 바로 알아차렸다.
일단 우리는 거리의 최대값을 구하는 것이므로 거리를 기준으로 이분탐색을 하면된다.
그리고 그 거리에 따라서 공유기가 최대 몇개 들어갈 수 있는 지 구하고 거리에 따른 공유기 개수랑 우리가 정한 공유기가 같거나 크면 을 조건으로 이분탐색하면 거리가 최대인 값을 구할 수 있다. 흐.....
이분탐색은 정렬이 필수다잇
예를 들면 1 2 4 8 9 인 거리 값이 있고 공유기는 3개 설치하려 할때 최대 거리 값은
거리가 1이면 1 2 4 8 9
o o o o o 공유기 5개 설치
거리가 2면 1 2 4 8 9
0 0 0 공유기 3개 설치
거리가 3이면 1 2 4 8 9
o o o 공유기 3개 설치 → 거리 최대 답:3
거리가 4이면 1 2 4 8 9
o o 공유기 2개 설치
이런 방식으로 이분탐색해서 답을 구했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,c;
bool check(vector<long long>& v,int x){ //임의의 거리 x값
long long last=v[0];
int cnt=1;
for(int i=1;i<n;i++){
if((v[i]-last)>=x){ // 공유기 설치한 마지막 집과 i의 집거리 차이가 x값보다 크거나 같으면
last=v[i];
cnt++;
}
}
return cnt>=c; //공유기 설치 개수가 지정한 공유기 개수보다 크거나 같으면 참
}
int main(){
cin>>n>>c;
vector<long long> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.begin(),v.end());
long long left=1; //거리 최소는 1
long long right=v[n-1]-v[0]; //거리 최대는 마지막 집에서 처음 집거리 뺀거
long long ans=1;
while(left<=right){ //거리를 값으로 이분 탐색
long long mid=(left+right)/2;
if(check(v,mid)){
left=mid+1;
if(ans<mid){
ans=mid;
}
}
else{
right=mid-1;
}
}
cout << ans;
}