(매일 BOJ) C++ 17266번 어두운 굴다리

이번 문제는 17266번 어두운 굴다리이다.

접근법

• 특정 밝기 거리 X를 기준으로, 가로등들이 굴다리 전체를 커버할 수 있는지를 확인한다.
• 이분 탐색을 통해 최소한의 X를 찾는다.

알고리즘 설계

1. 이분 탐색 범위는 start = 1, end = N
2. X가 주어졌을 때, 가로등이 굴다리 [0, N]을 모두 커버할 수 있는지를 판단
3. 판단 기준
   • 첫 번째 가로등이 0보다 멀면 안 됨 → pos[0] - X > 0이면 실패
   • 두 가로등 사이가 비면 안 됨 → pos[i+1] - pos[i] > 2 * X이면 실패
   • 마지막 가로등이 끝까지 도달해야 함 → pos.back() + X < N이면 실패

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int length;
    cin >> length;
    int num;
    cin >> num;
    vector<int> location;
   

    for(int i = 0; i < num; i++){
        int n;
        cin >> n;
        location.push_back(n);
    }


    int start = 1,end = length;
    int answer = 0;

    while (start <= end) {
        int mid = (start + end) / 2;
        bool can_light = true;

        // 왼쪽 끝 확인
        if (location[0] - mid > 0) can_light = false;

        // 중간 구간 확인
        for (int i = 0; i < num - 1; i++) {
            if (location[i+1] - location[i] > 2 * mid) {
                can_light = false;
                break;
            }
        }

        // 오른쪽 끝 확인
        if (location.back() + mid < length) can_light = false;

        if (can_light) {
            answer = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    cout << answer;
}