[백준] 10766 Trapped in the Haybales

해석하는데 1시간 넘게 걸렸다 ㅎㅎ

1~10억 사이의 길에 P라는 위치에 높이 S 짜리 막대기를 놓는다고 생각하면 편하다. 그 후 만약 막대 사이의 거리가 막대보다 높다면 부수기 가능

N이 4000이니까 완탐을하자

양쪽 방향으로 가서 탈출 가능하다면 넘기고 

불가능하다면 답에 더하자

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
pair<int, int> arr[4444];
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %d %d", &arr[i].second, &arr[i].first);
    sort(arr, arr + n);
    int ans = 0;
    for (int i = 0; i < n-1; i++) {
        int l = i, r = i + 1;
        bool ok = false;
        while (1) {
            if (l == -1 || r == n) {
                ok = true; break;
            }
            int sum = arr[r].first - arr[l].first;
            if (sum <= arr[l].second && sum <= arr[r].second) break;
            if (sum > arr[r].second) r++;
            if (sum > arr[l].second)  l--;
        }
        if (!ok) ans += arr[i + 1].first - arr[i].first;
    }
    printf("%d\n", ans);
}