백준 2110 C++ (공유기 설치)

이분탐색에 유독 약한건지, 공부가 제대로 안된건지ㅜ

한 문제 한 문제 해결하는데 시간도 오래걸리고 잘 풀리지 않는다.

이번 문제도 그랬다.

이분탐색(이 문제는 upper_bound) 부분에서 틀린 것은 아니고, 문제를 해석하는 능력이 다소 부족했던것 같다.

시간 제한	메모리 제한	정답률
2초	128MB	41.494%

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

핵심

공유기 간 최소거리는 1, 최대 거리는 마지막 집에서 처음 집 좌표를 뺀 값이다.
아참, 이 문제 얍삽하게도 집 좌표를 정렬하지 않고 주기 때문에, 받자마자 정렬부터 해야한다.
인접공유기간 최대거리를 하나하나 다 계산하기엔 n이 너무 크기 때문에, 이분탐색을 해야한다.(upper_bound)
bool chk(long long d) : 가장 인접한 거리가 d이상일 때, 공유기 c개를 설치할 수 있는가?

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


using namespace std;

int n, c;
long long tmp, l, r, maxx, mid, answer;
vector<long long> houses;

long long search(long long target){
    long long leftt, rightt, midd;
    
    leftt = 0;
    rightt = n-1;
    
    while(leftt <= rightt){
        midd = (leftt + rightt) / 2;
        
        if(target == houses[midd]){
            return midd;
        }
        else if(target > houses[midd]){
            leftt = midd + 1;
        }
        else{
            rightt = midd - 1;
        }
    }
    
    return -1;
}


bool chk(long long d){
    
    long long cnt = 1;
    long long prev = houses[0];
    
    for(int i=1;i<n;i++){
        if(houses[i] - prev >= d){
            cnt++;
            prev = houses[i];
        }
    }
    
    if(cnt >= c) return true;
    return false;
    
    //처음에 짰던 실패코드. chk(d)함수를 가장 인접한 거리가 "정확히" d인지를 체크했다.
    /*
    for(long long first=0;first<n;first++){
        long long cnt = 2;
        long long second = search(houses[first]+d);
        
        if(second != -1){
            for(int i=first-1;i>=0;i--){
                if(houses[first] - houses[i] >= d){
                    cnt++;
                    first = i;
                }
            }
            
            for(int i=second+1;i<n;i++){
                if(houses[i] - houses[second] >= d){
                    cnt++;
                    second = i;
                }
            }
            
            if(cnt >= c)return true;
        }  
        
        
    }
    
    return false;
    */
}


int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> c;
    
    for(int i=0;i<n;i++){
        cin >> tmp;
        houses.push_back(tmp);
        
        if(maxx < tmp){
            maxx = tmp;
        }
    }
    
    sort(houses.begin(), houses.end());
    
    l = 1;
    r = maxx - houses[0];
    
    while(l <= r){
        mid = (l + r) / 2;
        
        if(chk(mid)){
            answer = mid; //l은 mid+1이라서 마지막으로 성공한 값을 저장하지 못하므로 ans에 저장
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
	
    cout << answer << '\n';

    
	return 0;
}