[백준 12865] 공유기 설치

공유기 설치

문제설명

공유기를 설치하는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 값을 구하자

알고리즘

1. 값을 각각 입력 받고 오름차순으로 정렬한다.
2. left를 1로, right를 최대 거리(제일 큰 값-제일 작은 값)로 설정한다.
3. 이분 탐색 알고리즘을 사용하는데, 현재 집의 거리와 mid를 비교하여 더 크면 prev값을 업데이트하고 count를 증가시킨다.
4. count가 알맞은 값이 오면 종료 시킨다.

---

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX 200001
using namespace std;

int arr[MAX];

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

    int N, C;
    cin >> N >> C;

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

    sort(arr, arr + N);//오름차순 정렬
    int answer = 0;

    int left = 1 , right=arr[N-1]-arr[0];
    while (left<=right)
    {
        int    mid = (left+right) / 2;
        int prev = arr[0];
        int count = 1; 
        for (int i = 0; i < N; i++)
        {
            int dis = arr[i] - prev;
            if (dis>=mid)
            {
                count++;
                prev = arr[i];
            }
        }
        if (count >= C)
        {
            left = mid + 1;
            answer = mid;
        }
        else
        {
            right = mid - 1;
        }

    }
    cout << answer;

    return 0;
}