2110번: 공유기 설치

2110번:  공유기 설치

사용 언어: C++

 

풀이

공유기들 사이의 거리를 최대한 크게 둬야하기 때문에 이분 탐색을 생각하면 된다.

1) 이분 탐색을 쓰려면 일단 정렬 -> sort

2) 공유기 사이의 최대 거리 구하기

 

최대 거리를 구하려면 일단 첫 번째 집과 마지막 집을 시작과 끝으로 잡고 이분탐색을 시작한다.

두 집의 중간 거리 값이 가능한지 canPlaceRouters(거리)를 통해 확인한다. 저 함수에서는 모든 집들 사이에 받은 (거리)만큼 떨어진 집에 설치가 가능한지 확인하고, 설치가 가능하면서 설치한 개수가 총 개수와 같다면 true를 리턴한다.

canPlaceRouters가 true라면 low = mid + 1로 mid 거리를 벌려 더 큰 경우가 가능한지 확인하고, 만약  false라면 high = mid - 1로 더 작은 거리에서는 가능한지 확인한다.

#include <bits/stdc++.h>
using namespace std;

int N, C;
vector<int> houses;

// 공유기를 주어진 거리 `d` 이상으로 배치할 수 있는지 확인
bool canPlaceRouters(int d)
{
    // 첫 번째 집은 무조건 공유기 설치
    int count = 1;
    // 가장 최근 공유기 설치한 집
    int lastInstalled = houses[0];

    for (int i = 1; i < N; i++)
    {
        // 공유기 설치 가능하면 설치
        if (houses[i] - lastInstalled >= d)
        {
            count++;
            lastInstalled = houses[i];
        }
        // 설치된 수가 총 공유기 개수면 return true
        if (count >= C) return true;
    }

    return false; // C개 설치 불가능
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> C;
    houses.resize(N);

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

    // 1. 집 좌표 정렬
    sort(houses.begin(), houses.end());

    // 2. 이분 탐색으로 가장 인접한 공유기 사이의 최대 거리 구하기
    int low = 1;  // 최소 거리
    int high = houses[N - 1] - houses[0];  // 최대 거리
    int answer = 0;

    while (low <= high)
    {
        int mid = (low + high) / 2;  // 중간 거리
        if (canPlaceRouters(mid))
        {
            answer = mid;  // 가능한 거리라면 일단 저장
            low = mid + 1;  // 더 큰 거리 시도
        }
        else
        {
            high = mid - 1;  // 불가능한 거리면 거리 줄이기
        }
    }

    cout << answer << "\n";
}