[백준(BOJ)] 어두운 굴다리(17266번)_C++

커버해야 할 가장 긴 길이를 구하면 되는 문제다.

 

함정아닌 함정이 있다면

-거리의 시작과 첫번째 가로등간의 거리

-가로등간의 거리

-마지막 가로등과 거리의 끝간의 거리

위의 3가지를 잘 구분해서 구해야 한다는 것이다.

 

가로등은 양옆으로 비출 수 있기 때문에 특히 가로등간의 거리는 그 값의 절반만을 취해야 한다.

때문에 3가지를 구분해서 구해야 하고, 그러면 쉽게 통과할 수 있을 것이다.

 

---

정답 코드

#include <iostream>

using namespace std;

int n, m, s, e, Max;
bool road[100'001];

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

    //input
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x;
        cin >> x;
        road[x] = true;

        if (i == 0)
            s = x;
        if (i == m - 1)
            e = x;
    }

    //check s ~ e
    int pre = s;
    for (int i = s + 1; i <= e; i++){
        if (road[i] == true){
            Max = max(Max, i - pre);
            pre = i;
        }
    }
    Max = Max % 2 == 0 ? Max / 2 : Max / 2 + 1;

    //find max range
    Max = max(Max, s);
    Max = max(Max, n - e);

    //output
    cout << Max;
}