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

https://www.acmicpc.net/problem/2110

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

using namespace std;

vector<int> arr;


int main() {

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

    int n, c;
    int ans = 0;
    cin >> n >> c;

    arr.resize(n);


    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());


    int s = 1;
    int e = arr.back() - arr.front();



    while (s <= e) {
        int mid = (s + e) / 2;

        int cnt = 1;
        int st = arr.front();

        for (int i = 1; i < n; i++) {
            if (arr[i] - st >= mid) {
                cnt++;
                st = arr[i];
            }
        }

        if (cnt >= c) {
            ans = max(ans, mid);
            s = mid + 1;
        } else {
            e = mid - 1;
        }

    }


    cout << ans;





    return 0;
}

1. 문제

수직선상에 n개의 집의 좌표가 주어진다. 이 중 c개의 집을 골라 공유기를 설치하려 한다. 공유기는 한 집에 하나만 설치할 수 있고, 인접한 공유기 사이의 거리를 가능한 크게 잡으려고 한다. 이 때 그 거리를 구하라.

2. 풀이

꽤나 어려운 문제였다. 이 문제의 아이디어는 다음과 같다.

1. 가장 왼쪽에 있는 집에 공유기를 설치한다.
2. 인접한 공유기 사이의 거리로 이분탐색을 한다. 해당 거리를 넘어갈 때 마다 공유기를 설치한다.
3. 공유기의 개수 미달이면 더 많이 설치하기 위해 낮은 범위에서, 이상이면 최적해를 찾기 위해 더 높은 범위에서 거리를 찾는다.

한번 구현해보자.

 sort(arr.begin(), arr.end());


    int s = 1;
    int e = arr.back() - arr.front();

입력받은 집의 좌표를 정렬, 집 사이의 거리는 1 이상이고, 양 끝 집의 거리가 최대이므로 이를 e로 설정한다.

 while (s <= e) {
        int mid = (s + e) / 2;

        int cnt = 1;
        int st = arr.front();

        for (int i = 1; i < n; i++) {
            if (arr[i] - st >= mid) {
                cnt++;
                st = arr[i];
            }
        }

        if (cnt >= c) {
            ans = max(ans, mid);
            s = mid + 1;
        } else {
            e = mid - 1;
        }

    }

인접한 공유기 간의 최대 거리를 가지고 이분탐색을 수행한다. cnt는 가장 왼쪽의 위치에 미리 설치했으므로 1로 초기화하고, 각 집을 돌면서 해당 거리를 넘어갔을 경우 그 집에 공유기를 설치한다.

공유기의 개수 미달이면 더 많이 설치하기 위해 낮은 범위에서, 이상이면 ans를 갱신해준다. c가 현재 설치한 공유기 초과라 해도 오른쪽부터 공유기를 하나씩 없애가면서 c를 맞출 수 있다. 최적해를 찾기 위해 더 높은 범위에서 거리를 찾는다.

 

연산이 끝나고 ans를 출력하면 정답을 구할 수 있다.