[C++] 백준 17266번 어두운 굴다리

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

풀이

가로등의 높이는 최소 1, 최대 n이다. 이 범위에서 굴다리를 모두 비추기 위한 가로등의 최소 높이를 빠르게 구하기 위해 이분탐색을 사용하였다.

가로등의 높이를 height이라고 할 때, 가로등을 설치하려는 위치 배열 pos의 어떤 두 원소의 차가 2 * height보다 크면 안 된다.

이 조건을 만족하는 가장 작은 height을 구했다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> pos;

bool isValid(int height) {
    if(pos[0] > height) return false;
    
    int range = 2 * height;
    for(int i=1; i<m; i++) {
        if(pos[i] - pos[i-1] > range) return false;
    }
    
    if(n - pos[m-1] > height) return false;
    
    return true;
}

int binarySearch() {
    int start = 0;
    int end = n;
    int mid = (start + end) / 2;
    int ans = end;
    
    while(start <= end) {
        if(isValid(mid)) {
            ans = mid;
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
        mid = (start + end) / 2;
    }
    
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    pos.resize(m);
    for(int i=0; i<m; i++) cin >> pos[i];
    
    cout << binarySearch();
    
    return 0;
}