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

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M;
vector<int> pos;

bool posibleAllBright(int height) {
    int position = 0;

    for (int curr : pos) {
        int leftLight = curr - height;
        int rigntLight = curr + height;

        if (position < leftLight)
            return false;

        position = rigntLight;
    }

    if (position >= N)return true;
    else return false;
}


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

    
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int tmp;
        cin >> tmp;
        pos.push_back(tmp);
    }
    
    int lo = 0;
    int hi = N;
    int mid = ((lo + hi) / 2);

    while (lo != hi) {

        if (hi - lo <= 1) {
            if (posibleAllBright(hi)) {
                lo = hi;
            }
            else {
                hi = lo;
            }

            break;
        }

        if (posibleAllBright(mid)) {
            hi = mid;
            mid = ((lo + hi) / 2);
        }
        else {
            lo = mid;
            mid = ((lo + hi) / 2);
        }
    }

    cout << lo;

   
}

 

가로등의 높이가 10만까지 가능하고

가로등의 개수또한 10만까지 가능하다.

가로등의 높이의 경우 N의 높이이면 항상 가능하다.

이후 0~N범위의 이분탐색을 통해 적절한 가로등의 높이를 찾을 수 있다.