백준 2110 공유기 설치

문제

[2110 문제 링크]

풀이

공유기 사이의 "간격"을 이분 탐색으로 찾는다.

예를 들어 간격이 3이라면 첫 번째 집에 공유기를 설치하고, 두 번째 집부터 돌면서 이전 공유기와의 간격이 3이상인지 확인한다. 간격이 3 이상이라면 그 집에 공유기를 설치하고 다음 집을 탐색하며 간격 계산을 반복한다.

모든 집을 확인했을 때 설치된 공유기가 c보다 많으면 간격을 늘리고(right = gap - 1), c보다 작거나 같으면 간격을 줄인다(left = gap + 1)

소스코드

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, c;
    cin >> n >> c;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());

    int left = 1;
    int right = vec[n - 1] - vec[0];
    int ans = 0;

    while (left <= right) {
        int gap = (left + right) / 2;
        int cnt = 1;
        int bef = vec[0];
        for (int i = 1; i < n; i++) {
            if (vec[i] - bef >= gap) {
                cnt++;
                bef = vec[i];
            }
        }
        if (cnt >= c) {
            ans = gap;
            left = gap + 1;
        } else {
            right = gap - 1;
        }
    }

    cout << ans;

    return 0;
}

이분탐색 코드의 틀은 그냥 외워버리자

 while (left <= right) {
        int mid = (left + right) / 2;
        
        // mid 값으로 계산했을 때 조건을 만족하는 경우가 얼마나 되는지 구한다. 
        // 이 값을 cnt라고 하고, 최종적으로 만족해야 하는 값은 c라면
        if ( cnt >= c) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }