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

문제 링크

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

2110번: 공유기 설치

 

문제 설명

수직선에 N개의 집이 있고 각각의 집의 좌표는 0부터 1,000,000,000 값을 갖는다.

하나의 집에 최대 1개의 공유기를 총 C개 설치하는데, 가장 인접한 두 공유기 사이의 최대 거리를 구해야 한다.

 

사고 과정

집의 좌표는 크기 순서대로 주어지지 않지만 집 사이의 거리는 좌표의 순서에 영향을 받기 때문에,

집의 좌표를 입력 받고 오름차순으로 정리해줘야 한다는 생각이 들었다.

정렬 이후에 집에 공유기를 배치 해야 하는데, 모든 경우의 수를 따지면 O(N^2)이 되기 때문에 이분 탐색을 활용해야 했다.

 

하지만 이분 탐색을 어디에 적용해야 하는지 감이 안잡혔다..

입력 받은 집의 좌표에 대해 적용하자니 공유기를 여러 개 배치해야 하기 때문에 

사실상 모든 경우의 수를 따지는 것과 다름이 없고...

좌표에 이분 탐색을 적용하자니 공유기는 집에만 설치할 수 있기 때문에

선택된 좌표에 집이 존재 하는지와 다른 좌표는 또 어떻게 선택할 지 막막했다.

 

해결 방법

결국 다른 블로그를 참고해서 이해함ㅠ

https://jaimemin.tistory.com/966

 

결론은 이분 탐색을 거리에 적용해야 했다.

1. 입력받은 좌표를 오름차순으로 정렬한다.

2. 최소 거리와 최대 거리를 설정한다.

3. 거리에 대한 이분 탐색을 진행한다. 이 때 설정한 거리가 문제의 조건에 부합하는지 확인한다.

4. 3번 조건을 충족하는 거리 중, 최대 거리를 출력한다.

 

예시

백준에 제시된 예시를 활용해보자.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

void init();
void input();
bool isPossible(int num);
void solve();

int N, C;
int arr[200001];

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

void input()
{
    cin >> N >> C;

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

bool isPossible(int num)
{
    int cnt = 1;
    int prev = arr[0];

    for (int i = 1; i < N; i++)
    {
        if (arr[i] - prev >= num)
        {
            cnt++;
            prev = arr[i];
        }
    }

    if (cnt >= C)
        return true;
    return false;
}

void solve()
{
    sort(arr, arr + N);

    // 최소거리, 최대거리
    int low = 1;
    int high = arr[N - 1] - arr[0];
    int result = 0;

    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (isPossible(mid))
        {
            result = max(result, mid);
            low = mid + 1;
        }
        else
            high = mid - 1;
    }

    cout << result;
}

int main()
{
    init();
    input();
    solve();

    return 0;
}