[Binary Search] 백준 2110번 “공유기 설치” C++ 풀이

문제 링크

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

풀이

• 중요한 부분

  • 문제가 원하는 것은, 가장 인접한 두 공유기 사이의 거리가 최대인 것이지만,
  • 결국, 모든 공유기들의 간격이 공평하게 설치되기를 원한다고 해석할 수 있습니다.
  • 따라서, 모든 공유기들을 공평하게 설치할 수 있는 간격을 이분 탐색을 통해 찾아야합니다.

• 진행 순서

  1. 공유기 설치 좌표들을 오름차순으로 정렬합니다.
  2. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한 뒤, 공유기를 가장 공평하게 설치할 수 있는 간격(mid)을 구합니다.
  3. 첫 번째 집에 공유기를 설치한 뒤, 첫 번째 집에서 나머지 집들 간의 간격을 확인하며, mid 이상으로 떨어져 있는 집을 탐색합니다.
  4. 첫 번째 집으로부터 mid 이상 떨어진 집을 찾은 경우, 해당 집에 공유기를 설치한 뒤, 해당 집 기준으로 다시 mid 만큼 떨어져있는 집을 탐색합니다.
  5. 모든 집을 탐색했다면, 공유기 설치 간격을 이분법을 사용해 갱신합니다.
     1. 현재까지 설치한 공유기의 개수가 아직 C개 이하라면, 기존 간격이 너무 크다는 의미이므로, 기존 간격보다 더 작은 간격으로 갱신합니다.
     2. 현재까지 설치한 공유기의 개수가 C개 이상이라면, 기존 간격이 너무 작다는 의미이므로, 기존 간격보다 더 큰 간격으로 갱신합니다.
  6. 가능한 모든 간격들을 탐색할 때까지 이분법 과정을 3번~5번 반복합니다.
  7. 탐색된 최대 간격을 반환합니다.

• 그림으로 이해

  

코드

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

using namespace std;

// 공유기 위치 저장용 Vector
vector<int> router;

// 최대 간격을 가지는 공유기 위치 찾기
int find_max_dist(int n, int c){

    // 기준 간격 이분 탐색을 위한 변수
    int l_dist = 0;                     // 첫 번째 공유기에서 첫 번째 공유기까지의 간격
    int r_dist = router[n-1]-1;         // 첫 번째 공유기에서 마지막 공유기까지의 간격

    // 결과 간격
    int result_dist;

    // 이분법을 사용해, 모든 간격 탐색이 끝날때까지 진행
    while(l_dist<=r_dist){

        // 설치한 공유기 개수 (첫 번째 공유기는 설치하고 시작)
        int install_router = 1;

        // 기준 간격 갱신
        int mid_dist = (l_dist+r_dist)/2;   

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

        // 각 공유기의 간격 확인
        for (int i=1; i<n; ++i){

            // 간격 확인할 공유기 위치
            int end = router[i];

            // 공유기 간격이 기준 간격을 넘는지 확인한 뒤, 넘는 간격에는 공유기를 설치하고
            // 해당 위치를 다시 탐색 시작 위치로 변경
            if (end - start >= mid_dist){
                install_router += 1;
                start = end;
            }
        }

        // 공유기 간격 탐색이 끝난 뒤, 설치한 공유기 개수가 C개 이상이라면,
        if (install_router >= c){
            // 공유기 설치에 사용된 간격을 결과 간격으로 임시 저장
            result_dist = mid_dist;
            // 이분법을 사용한 간격 갱신 시, 이전보다 넓은 간격을 사용하기 위해, L 수정
            l_dist = mid_dist + 1;
        }
        // 설치한 공유기 개수가 C개 미만이라면,
        else{
            // 이분법을 사용한 간격 갱신 시, 이전보다 좁은 간격을 사용하기 위해, R 수정
            r_dist = mid_dist - 1;
        }
    }

    // 결과 거리 반환
    return result_dist;

}

int main(){

    // 공유기 개수, 설치 개수
    int n, c;
    cin >> n >> c;

    // 공유기 위치 입력
    int loc;
    for (int i=0; i<n; ++i){
        cin >> loc;
        router.push_back(loc);
    }

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

    // 공유기 간 최대 거리 탐색 함수 실행
    cout << find_max_dist(n, c);

}

참고

• https://mygumi.tistory.com/301
• https://katfun.tistory.com/entry/백준-2110번-공유기-설치