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

백준 2110번 : 공유기 설치

등급 : Gold IV

2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

사용 알고리즘 : Binary_Search

사용 자료구조 : Vector

 

이분탐색의 활용 방법과 이해도를 높여줄 수 있는 문제라고 생각한다.

인접한 두 공유기 사이의 거리를 이분 탐색으로 점점 줄여나가며 탐색하는 문제.

 

• Left 지정 : 같은 지점에 공유기가 있을 순 없으므로, 두 공유기 사이의 최소 거리인 1로 지정.
• Right 지정 : 입력받은 위치 값 중 가장 큰 수와 가장 작은 수(처음 위치와 끝 위치)가 두 공유기 사이의 최대 거리. 

위의 Left, Right 값으로 이분 탐색을 진행해 Mid를 구한 후, 배열의 원소끼리 간격을 Mid와 비교해 몇 개를 놓을 수 있는지 구하도록 한다.

 

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

using namespace std;

vector <int> v;
int n, c;
int ans = 0;

void bis(int left, int right)
{
    if (left > right) return;
    int mid = (left + right) / 2;
    int amt = 1;
    // 첫 번째 위치에는 공유기를 무조건 놓으므로 총량(amt)은 1로 놓고 시작한다.
    int start = v.front();
    // 마찬가지로 첫 번째 위치에는 공유기가 무조건 있으므로 start = v.front()로 지정.
    for (int i = 1; i < n; i++)
    {
        if (v[i] - start >= mid)
        // 두 지점 사이의 거리가 mid보다 크면 총량을 증가하고, 현재 공유기 위치를 시작 위치로 갱신.
        {
            amt++;
            start = v[i];
        }
    }
    if (amt >= c)
    // 총량이 원하는 공유기 갯수보다 많거나 같으면 간격을 답(ans)으로 저장하고, 최댓값을 구하기 위해 추가 조사.
    {
        if (ans < mid) ans = mid;
        bis(mid + 1, right);
    }
    else bis(left, mid - 1);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> n >> c;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    bis(1, v.back()-v.front());
    // 본문에 써있는 left, right 조건에 맞춰 이분 탐색 진행
    cout << ans;
}