이분 검색을 통해 해결한 문제였다. 이분 검색의 Start와 end Point는 최소 거리인 1과 처음 집과 끝집의 차이로 설정하였다.

end_point의 값을 처음 집과 끝집의 차이로 설정한 이유는 이분 검색을 통해 알고자 하는 것은 집 마다의 거리이기 때문에 가장 큰 차이를 알 수 있는 처음 집의 좌표가 끝 집의 좌표 차이를 이용한 것이다.

이분 검색 과정내에서 첫번째 집인 house[0]은 무조건 공유기를 설치해야 최대 값이 나올 확률이 크니 i = 1부터 탐색을 시작한다.

현재 거리인 mid보다 house[i] - low(전 집의 좌표)가 크거가 같다면 공유기를 설치 할 수 있으니 라우터의 갯수를 늘려주고 전 집의 좌표를 업데이트 한다. 위와 같은 과정을 통해 현재 라우터의 갯수가 c와 같거나 크다면 start의 갯수를 늘려 라우터의 갯수를 줄이거나 좀 더 타이트한 정답을 찾는다.

정답

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>

#define endl "\n"

using namespace std;
int n, c;
int low, high, mid;
int ans = 0;
vector<int> house;

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    
    cin >> n >> c;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        house.push_back(a);
    }

    int start = 1;
    sort(house.begin(), house.end());;
    high = house[n-1] - house[0];

 
    while (start <= high) {
        int router = 1;

        low = house[0];
        mid = (high + start) / 2;

        for (int i = 1; i < n; i++) {
            if (house[i] - low >= mid) {
                router++;
                low = house[i];
            }
        }

        if (router >= c) {
            ans = max(ans, mid);
            start = mid + 1;
        }
        else {
            high = mid-1;
        }

    }

    cout << ans;
    return 0;
}

오답

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>

#define endl "\n"

using namespace std;
int n, c;
int low, high, mid;
int ans = 0;
vector<int> house;

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    
    cin >> n >> c;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        house.push_back(a);
    }

    int start = 1;
    high = house[-1];
    sort(house.begin(), house.end());;
 
    while (start <= high) {
        int router = 1;

        low = house[0];
        mid = (high - start) / 2;

        for (int i = 1; i < n; i++) {
            if (house[i] > (low + mid)) {
                router++;
                low + mid;
            }
        }

        if (router >= c) {
            ans = max(ans, mid);
            start++;
        }
        else {
            high--;
        }

    }

    cout << ans << endl;

    return 0;
}