187. 공유기 설치

백준

1. 이진탐색 (파라메트릭 서치)

n, c = list(map(int, input().split()))
array = [int(input()) for _ in range(n)]
array.sort()

start = 1
end = array[-1] - array[0] #가능한 최대 거리(max gap)
result = 0

while(start <= end):
  mid = (start + end) // 2
  value = array[0]
  count = 1
  #현재 mid값을 이용해 공유기를 설치
  for i in range(1, n): #앞에서 부터 설치
    if array[i] >= value + mid:
      value = array[i]
      count += 1
  if count >= c: #c개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
    start = mid + 1
    result = mid #최적의 결과를 저장
  else: #c개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
    end = mid - 1

print(result)

2. C++

#include <bits/stdc++.h>

using namespace std;

// 집의 개수(N)와 공유기의 개수(C)
int n, c;
vector<int> arr;

int main() {
    cin >> n >> c;

    // 전체 집의 좌표 정보를 입력 받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 이진 탐색 수행을 위해 정렬 수행
    sort(arr.begin(), arr.end());

    int start = 1; // 가능한 최소 거리(min gap)
    int end = arr[n - 1] - arr[0]; // 가능한 최대 거리(max gap)
    int result = 0;

    while (start <= end) {
        // mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미
        int mid = (start + end) / 2;
        // 첫째 집에는 무조건 공유기를 설치한다고 가정
        int value = arr[0];
        int cnt = 1;
        // 현재의 mid 값을 이용해 공유기를 설치하기
        for (int i = 1; i < n; i++) { // 앞에서부터 차근차근 설치
            if (arr[i] >= value + mid) {
                value = arr[i];
                cnt += 1;
            }
        }
        // C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가시키기
        if (cnt >= c) {
            start = mid + 1;
            result = mid; // 최적의 결과를 저장
        }
        // C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소시키기
        else {
            end = mid - 1;
        }
    }

    cout << result << '\n';
}