[BOJ] 2110번 : 공유기 설치

문제 링크 : 백준 2110번

[문제 접근]

거리가 작은 값부터 대입해보면서 공유기 개수가 맞을 때까지 모든 경우 수를 찾는 방법은 시간초과가 난다.
풀이 방법을 찾지 못해서 다른 사람 코드를 참고했는데 이분 탐색으로 풀리는 것 같다.
두 공유기 사이의 최소 거리는 1, 최대 거리는 양 끝 공유기이므로 arr[n-1]-arr[0]이다.

1. check 함수에서 설치할 수 있는 최대 거리가 mid일 때 mid에 따라 공유기를 설치한다.
2. 설치된 공유기의 개수가 c보다 크거나 같으면 true를 반환, 아니면 false를 반환한다.
3. true라면 최대 거리를 더 늘려본다.(mid는 항상 최대값으로 갱신된다.) -> 결국 cnt == c인 값이 최대의 간격이다.
4. false라면 최대 거리를 줄인다.

⭐ start == end까지 탐색하면 정답이 되는데 무조건 check함수에서 true가 나오므로 start = mid+1 후 start>end가 되어서 while문을 빠져나온다.

따라서 정답은 start-1

[소스 코드]

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

using namespace std;
int n,c;
vector<int> arr;

bool check(int mid) {
    int standard = arr[0];
    int cnt=1;
    for(int i=1 ; i<n ; i++) {
        if(arr[i]-standard>=mid) {
            cnt++;
            standard = arr[i];
        }
    }
    if(cnt>=c) return true;
    else return false;
}

int main(){
    cin >> n >> c;
    for(int i=0 ; i<n ; i++) {
        int a;
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end());

    int start = 1, end = arr[arr.size()-1]-arr[0]; // 최소 거리, 최대 거리
    int ans=0;
    while(start<=end) {
        int mid = (start+end)/2;

        if(check(mid)) start = mid+1;
        
        else end = mid-1;
        
    }
    cout << start-1;

    return 0;
}