BOJ - 2110 ) 공유기 설치

---

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

2110번: 공유기 설치

서로다른 지점에 공유기를 설치하면서 가장 멀리 떨어지게 설치하는 거리를 구하는 문제이다.

 

첫번째에 놓았다면, FOR문을 돌면서 나머지와의 거리를 계산해주고 CNT로 그 값을 반환하여서 C와 비교하면서

 

거리값인 MID를 이분탐색으로 업데이트해준다.

 

처음에 LEFT 를 배열중 가장작은값으로 초기화 시켰는데 틀렸습니다가 나와서 

 

LEFT 를 0부터 증가시켰더니 통과 됐다.

 

여기서 MID는 거리를 의미하는데 LEFT를 배열의 가장작은 값으로 초기화시키면

 

그보다 작은 값에서 정답이 나올경우를 체크 못해주어서 그렇다.

---

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int n, c;
vector< long long> num;
long long ans;
void input() {
    cin >> n >> c;
    for (int index = 0; index < n; index++) {
        long long t; cin >> t;
        num.push_back(t);
    }
 
}
 
long long count(long long mid) {
    long long cnt = 1;
    long long pos = num[0];
    for (int index = 0;  index < n; index++) {
        if (num[index] - pos >= mid) {
            cnt++;
            pos = num[index];
        }
    }
    return cnt;
}
void solution() {
 
    sort(num.begin(), num.end());
    
    long long left =  1;
    long long right = num[n - 1];
    long long mid;
 
    while (left <= right) {
 
        mid = (left + right) / 2;
 
        long long cnt = count(mid);
        if (cnt < c) {
            right = mid - 1;
        }
        else {
            ans = mid;
            left = mid + 1;
        }
    }
    cout << ans;
}
 
int main(void) {
 
    input();
    solution();
    return 0;
}

---