(2110) 공유기 설치

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

단계별로 풀어보기

25단계(이분 탐색) 5번째

 

 

 

보통 이분 탐색 문제가 어려운 경우는 두 가지이다. 애초에 문제가 이분 탐색 문제인지조차 모르겠을 때, 결정 함수를 어떻게 짜야 할 지 모르겠을 때.

이 문제에서 결정 함수는 이렇게 짜면 된다. 공유기를 설치 가능한 최소 좌표 d(초기값 0)와 설치한 공유기 수 cnt를 만든다.

오름차순으로 정렬한 집의 좌표를 순서대로 탐색하며 d보다 작으면 넘어가고, d보다 크면 새로운 좌표(집의 좌표+현재 탐색중인 값)를 설정하고 cnt를 1 증가시킨다. 마지막까지 탐색이 끝났을 때 cnt가 c보다 크면 현재 탐색중인 값으로 공유기 설치가 가능한 것이므로 더 크거나 같은 구간에서 찾고, 아니라면 더 작은 구간에서 찾는다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, c;
  
  cin >> n >> c;
  
  vector<int> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  sort(v.begin(), v.end());
  
  int lo= 1, hi= 1000000001;
  
  while(lo+1<hi){
    int mid= (lo+hi)/2;
    int d=0, cnt= 0;
    
    for(int i=0;i<n;i++){
      if(v[i]<d)  continue;
      
      d= v[i]+mid;
      cnt++;
    }
    
    (cnt>=c ? lo : hi)= mid;
  }
  
  cout << lo;
  
  return 0;
}