BOJ 2110 - 공유기 설치(C++)

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

2110번: 공유기 설치

 

풀이

두 공유기 사이의 거리에 대해 이분탐색을 이용

초기 값 -> left = 1, right = 공유기의 최대 좌표

1. mid = (left + right)/2 <----- 공유기 사이의 거리

2. 1번의 mid 값으로 전체 좌표에서 공유기를 몇개를 설치해야하는지 확인

3. 2번의 결과가 C(공유기 개수)보다 작으면 현재 거리(mid)가 너무 크게 설정한거기 때문에 right = mid-1 후 1로 돌아감

   반대로 크거나 같다면 현재 거리(mid)를 작게 설정했거나 더 거리가 커졌을때도 가능할 수 있기 때문에 left = mid+1로 설정후 1로 돌아감

 

* 현재 mid(탐색 거리)에 대한 검사를 할때, 현재 좌표 + 거리인줄 알고 if(arr[i] - before > mid)로 했었는데 테스트 결과가 실패했음

  문제에서의 거리는 공유기가 설치된 좌표까지 포함하는 거 였음 if(arr[i] - before >= mid)

  ex) 1, 3, 4 이고 거리가 2라고 했을 때, 1에서 공유기를 설치했다면 (1, 2)로 거리가 2임

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    vector<int> arr;
    int N, M;
    int ans=0;
    cin >> N >> M;
 
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        arr.push_back(num);
    }
    // 혹시나 오름차순으로 입력이 안 주어질까봐
    sort(arr.begin(), arr.end());
 
    int left = 1;
    int right = arr[arr.size() - 1];
    int mid;
    int before,set_num;
    while (left <= right) {
        mid = (left + right) / 2;
        before = arr[0];
        set_num = 1;
        for (int i = 1; i < N; i++) {
            if (arr[i] - before >= mid) {
                before = arr[i];
                set_num++;
            }
        }
        if (set_num >= M) {
            left = mid + 1;
            ans = mid;
        }
        else
            right = mid - 1;
    }
    cout << ans;
    return 0;
}