BOJ 20928 - 걷는 건 귀찮아

BOJ 20928 - 걷는 건 귀찮아

DP나 그리디 풀이가 있는 모양이지만, 스택으로 풀었다.

다음과 같이 구간이 있다고 하자.

$[s_i, e_i]$ 에 있어 $e_i$ 에 대해 단조성을 유지한다.

일단 $3$번 구간은 필요가 없다. 현재 스택에서 가장 오른쪽으로 긴 구간보다 오른쪽이 작기 때문이다. 따라서 스택에 넣어주지 않는다.

우리가 $5$번 구간을 볼 때, $2,4$ 번 구간은 pop 해준다. 왜냐면 $1$번 구간의 오른쪽이 $5$번 구간의 왼쪽 이상에 있기 때문에 $2,4$ 구간을 쓸 필요가 없기 때문이다.

이런식으로 스택을 쭉 구성하고 $e_i \ge m$ 이 되는 곳까지만 사용하면 된다.

$m$까지 도달할 수 없는 경우는 스택을 모두 구성했을 때 가장 오른쪽으로 긴 구간이 $m$ 이하이거나

중간에 구간이 끊기는 부분이 하나라도 있다면 불가능하다.

void solve() {
   int n, m;
   cin >> n >> m;
   vector<pi> a(n);
   vi p(n), x(n);
   fv(p);
   fv(x);
   vi dist(n, 1e9);
   dist[0] = 0;
   for (int i = 0; i < n; i++) {
      a[i] = {p[i], p[i] + x[i]};
   }
   vector<pi> t;
   t.pb(a[0]);
   for (int i = 1; i < n; i++) {
      if (sz(t) && t.back().se >= a[i].se) continue;
      while (sz(t) >= 2 && t[sz(t) - 2].se >= a[i].fi) t.pop_back();
      if (t.back().se < a[i].fi) {
         cout << -1;
         return;
      }
      t.pb(a[i]);
   }
   for (int i = 0; i < sz(t); i++)
      if (t[i].se >= m) {
         cout << i;
         return;
      }
   cout << -1;

}