[백준/C++] 2110번 공유기 설치

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

2110번: 공유기 설치

문제 분석

코드

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

using namespace std;

int n, c,x;
vector<int> v;

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

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

    // 공유기 위치 정렬
    sort(v.begin(), v.end());

    int left = 0, right = v[n - 1];

    int res;

    while (left <= right) {
        int install_router = 1;

        int mid = (left + right) / 2;

        // 첫 번째 공유기 위치
        int start = v[0];

        // 각 공유기의 간격 확인
        for (int i = 1; i < n; ++i) {
            // 간격 확인할 공유기 위치
            int check_install = v[i];

            // 공유기 간격이 기준 간격을 넘는지 확인한 뒤, 넘는 간격에는 공유기를 설치하고
            // 해당 위치를 다시 탐색 시작 위치로 변경
            if (check_install - start >= mid) {
                install_router += 1;
                start = check_install;
            }
        }
        // 공유기 간격 탐색이 끝난 뒤, 설치한 공유기 개수가 C개 이상이라면,
        if (install_router >= c) {
            // 공유기 설치에 사용된 간격을 결과 간격으로 임시 저장
            res = mid;         
            left = mid + 1;
        }
        // 설치한 공유기 개수가 C개 미만이라면,
        else {
            right = mid - 1;
        }
    }
    cout << res;
    return 0;
}

문제풀이

집의 좌표가 최대 10억인 점을 보아, 이분 탐색으로 풀 수 있다는 점을 알 수 있다.

1. 공유기 설치 좌표를 오름차순으로 정렬 (sort함수 이용, 정렬은 이분 탐색의 base)

2. 첫번째 공유기의 위치 = left, 마지막 공유기의 위치 = right로 두고, mid를 (left+right)/2로 설정

3. 우선 첫번째 집에는 공유기가 설치 되어야 최대 간격을 구할 수 있으므로, 첫번째 집에 공유기 설치

4. 그리고 첫번째 집에서부터 나머지 집들 간의 간격을 확인하며, mid보다 크거나 같은 것을 탐색

5. 만약 mid보다 크거나 같다면, 해당 집에 공유기를 설치하고, 해당 집에서부터 다시 탐색

6. 모든 집을 탐색했다면, mid를 재 조정

-> 설치된 공유기가 C개 미만이라면, 간격이 너무 크므로 right를 mid-1로 설정

-> 설치된 공유기가 C개 이상이라면, 간격이 너무 작으므로 left를 mid+1로 설정

3~6번 과정을 반복한다.

while문이 종료되었을 때 탐색된 최대 거리 출력

​

 

※ 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000이다.

-> 값이 10억이상으로 설정된 경우 이진탐색을 고려

-> logX나 √X의 시간복잡도를 가진다고 생각하고 방법을 생각해야 한다.

 

※ 10억은 약 2^33승이므로, x=2^33승일 때 O(log x)는 대략 30이다.

 

※ 이진 탐색으로 O(N*logX)에 문제를 해결할 수 있다.

- 20만 * 30 = 600만