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

2110번: 공유기 설치

이분 탐색을 이용한 문제이다. 시작과 끝을 집 양 끝으로 두고 반복문을 시작한다. 반복문을 돌면서 mid를 구해 집 간 거리가 이보다 크면 카운트를 한다. 만약 카운트가 C보다 크면 mid값을 키우기 위해 start를 옮겨주고 반대면 end를 옮겨준다. 이를 반복하면서 start가 옮겨질 때 mid값을 저장해 출력해주었다.
생각보다 시간이 걸린 문제였다. 이분 탐색도 많이 봐두자.

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

using namespace std;

int N, C, res = 0;
vector<int> v;

void binarySearch() {
    int start = 0;
    int end = v[N - 1];

    while (start <= end) {
        int mid = (start + end) / 2;
        int count = 1;
        int tmp = 0;

        for (int i = 1; i < N; i++) {
            if ((v[i] - v[tmp]) >= mid) {
                tmp = i;
                count++;
            }
        }

        if (count >= C) {
            res = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
}

void solution(){
    sort(v.begin(), v.end());
    binarySearch();

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> C;

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

    solution();

    return 0;
}