[알고리즘] 공유기 설치

구현 방식

• 가장 인접한 두 공유기 사이의 최대 거리를 구하기 위해 이분 탐색을 한다.
• 최소값은 0, 최대값은 정렬한 집의 위치 좌표벡터의 첫값과 끝값의 차이
• 현재 탐색하고 있는 거리를 k라고 할때
• 일단 맨처음 0 번째 집에 공유기를 배치한다고 가정하고 k 이상 떨어진 거리에 위치한 집에 공유기를 배치한다.
• 공유기를 모두 다 배치할 수 있으면 true 아니면 false를 리턴한다.

#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <map>

using namespace std;
void solution(int N, int C, vector<long long>& houses);
long long binarySearch(int N, int C, vector<long long>& houses);
bool canPlacedWithInDistance(int placeCount, long long distance, vector<long long>& houses);


int main()
{
    int N, C;

    cin >> N >> C;
    vector<long long> houses = vector<long long>(N);
    for (int i = 0; i < N; ++i)
        cin >> houses[i];
    
    sort(houses.begin(), houses.end());
    solution(N, C, houses);
}

void solution(int N , int C, vector<long long>& houses)
{
    cout << binarySearch(N, C, houses);
}

long long binarySearch(int N, int C, vector<long long>& houses)
{
    long long minDistance = 1;
    long long maxDistance = houses[N - 1] - houses[0];
    long long midDistance = (maxDistance + minDistance) / 2;
    long long result = LLONG_MIN;

    while (minDistance <= maxDistance)
    {
        if (canPlacedWithInDistance(C, midDistance, houses))
        {
            result = max(result, midDistance);
            minDistance = midDistance + 1;
        }
        else
            maxDistance = midDistance - 1;
        midDistance = (maxDistance + minDistance) / 2;
    }
    return result;
}

bool canPlacedWithInDistance(int placeCount, long long distance, vector<long long>& houses)
{
    long long recentPlacedPos = houses[0];
    placeCount--;
    for (auto& pos : houses)
    {
        if (placeCount <= 0)
            break;
        if (distance <= pos - recentPlacedPos)
        {
            recentPlacedPos = pos;
            placeCount--;
        }
    }

    if (placeCount <= 0)
        return true;
    else
        return false;

}