[백준 2110번] 공유기 설치(C++ / 이진탐색)

문제를 간단히 요약하면 공유기를 설치할건데, 가능한 서로 떨어뜨려서 놓고싶다는 문제이다.

그 중 가장 가까운 공유기간의 거리를 최대로 하고싶다.

 

아이디어 

문제를 보고 N은 최대 20만, C는 N에 속해있으며, 집의 위치는 10억이다.

대략 1초의 연산속도를 1억번이라고 봤을 때, O(N)의 속도로 찾는다고 해도 좌표를 통해서 찾으면 10초가 소모되어 timeout이 날것이 분명하다.

그래서 처음엔 집위치 list N은 20만개이므로 이를 일단 정렬하고 가운데 집을 기준으로 어떻게 해보려고 갖은 방법을 시도하다가 결국 아래와 같은 풀이로 접근하게 되었다.

 

이진탐색 문제들을 풀다보면 이걸 이진탐색으로 어떻게 풀어야하지? 에서 꽉꽉막힌다. 답답하기 그지 없는데, 

'무엇을 이진탐색 할것인가'에서 무엇을 빠르게 생각해내는게 핵심이다. 위처럼 잘못된 방식으로 답이 안나오면 다른 방식도 고려해봐야한다.

문제에서 '최대거리'를 요구하였으므로, 최대거리는 0번 좌표 ~ 10억번 좌표로 최대 10억을 가질 수 있을 것이다.

이를 선형탐색하는건 위에서 안된다고 말했으니, 10억은 약 2^30승 정도이므로 O(logN)의 탐색속도를 가지게 되면 30회 이내에 거리를 찾을 수 있다.

+ 아래 check함수에서 집 개수만큼 추가로 탐색하고 있으니 (for문, O(N)) (최대 30회 * 20만 = 600만 연산 이내에 해결)

 

그래서 이 문제는 O(NlogN) 속도로 해결이 가능하다고 생각한다.

 

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int N, C;
vector<int> x; // 집 좌표
int result = -1; // 최종 답
bool check(int mid){
	//첫번째 집 셋팅해두고 시작
    int cnt = 1; //사용되는 공유기 개수
    int prev = x[0]; // 일단 첫번째집.
    for(int i = 1 ; i< N; i++) // 모든집을 탐색할건데
    {
        if( x[i]-prev >= mid){ // 주어진 거리만큼 갈 수 있으면 
            cnt ++; //공유기 설치하고,
            prev = x[i]; // 해당집을 기준으로 다시 잡음.
        }
    }
    if(cnt >= C) return true; // 되는 조건이면 true, 더 큰 수 탐색해야함.
    else return false; // 안되는 조건이면 fasle, 더 작은 수 탐색해야함.
}

void b_search(){
    
    int left = 0; //0번 위치
    int right = x.back();//마지막 집 위치
    
    while(left <= right)
    {
        int mid = left+ (right-left)/2;
        //return true -> 큰 수 탐색 = left옮기기.
        if(check(mid)){
            left = mid+1;
            if(result <mid) // 최대값 찾기.
            	result = mid; 
            
        }
        //return false -> 작은 수 탐색 = right 옮기기.
        else right = mid-1;
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> C;
    for(int i = 0 ; i<N;i++)
    {
        int temp;
        cin >> temp;
        x.push_back(temp);
    }
    sort(x.begin(), x.end()); //정렬하고 시작.
    b_search();
    cout << result;
}