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

문제 링크: https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

문제 풀이에 이용된 알고리즘: 이분 탐색

 

수직선 상에 집들이 존재하고, 어떤 집들에 공유기를 설치할 수 있다고 할 때, C개 만큼만 설치하되, 공유기 간 인접한 거리 중 가장 가까운 거리가 최대가 되는 경우를 찾고, 그 때의 인접한 공유기 간 거리를 출력하는 문제이다.

 

집집 마다 공유기를 설치할 지 말 지, 결정하고 그 때의 공유기 수가 C개가 되는 지, 모든 경우의 수를 완전 탐색하여 충분히 풀 수 있는 문제이다.

 

하지만 입력이 굉장히 크기 때문에(혹은 입력의 크기랑은 상관없이) 굉장히 비효율적인 방법이란 것을 알 수 있다.

 

공유기 간 간격은 최소 1, 최대로는 abs(1 - Xn)만큼이 되므로, 공유기 간 간격을 이분 탐색하며 각 경우에서 설치된 공유기의 수가 C개 이상인지 확인하는 이분 탐색 방식으로 접근하였다.

 

좀 더 자세히는, 수직선의 1부터 공유기를 설치하고, 그 다음 집이 해당 step에서의 공유기 간 거리보다 멀리 떨어져 있을 경우에 새롭게 설치한다.

 

즉 가장 최근에 공유기를 설치한 집으로부터 현재 공유기 간 거리보다 멀리 떨어진 집에 새롭게 공유기를 설치해 나가는 것이다. 이렇게 하면 정확히 C개가 아니라, C개 이상 설치될 수 있다는 것을 주의깊게 생각해보길 추천한다.

 

/* BOJ 2110 공유기 설치 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, c, arr[200001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    int tmp_max = 0;
 
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        tmp_max = max(tmp_max, arr[i]);
    }
 
    sort(arr + 1, arr + 1 + n);
 
    unsigned int left = 1, right = tmp_max;
    int ans = 0;
 
    while (left <= right)
    {
        unsigned int mid = (left + right) / 2;
 
        int cnt = 1;
        int prev_house = arr[1];
 
        for (int i = 2; i <= n; i++)
        {
            // 공유기가 설치된 이전 집과 mid 이상 떨어진 경우에만 설치
            if (arr[i] - prev_house >= mid)
            {
                cnt++; // 설치
                prev_house = arr[i];
            }
        }
 
        if (cnt >= c) // 좀 더 공유기 설치 간격을 넓혀도 무방함
        {
            ans = max(ans, (int)mid);
            left = mid + 1;
        }
        else // 좀 더 촘촘히 공유기 설치해야함
            right = mid - 1;
    }
 
    cout << ans << endl;
 
    return 0;
}