BOJ 20928 - 걷는 건 귀찮아
DP나 그리디 풀이가 있는 모양이지만, 스택으로 풀었다.
다음과 같이 구간이 있다고 하자.
에 있어 에 대해 단조성을 유지한다.
일단 번 구간은 필요가 없다. 현재 스택에서 가장 오른쪽으로 긴 구간보다 오른쪽이 작기 때문이다. 따라서 스택에 넣어주지 않는다.
우리가 번 구간을 볼 때, 번 구간은 pop 해준다. 왜냐면 번 구간의 오른쪽이 번 구간의 왼쪽 이상에 있기 때문에 구간을 쓸 필요가 없기 때문이다.
이런식으로 스택을 쭉 구성하고 이 되는 곳까지만 사용하면 된다.
까지 도달할 수 없는 경우는 스택을 모두 구성했을 때 가장 오른쪽으로 긴 구간이 이하이거나
중간에 구간이 끊기는 부분이 하나라도 있다면 불가능하다.
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;
}
Comments