BOJ 10129 작은 새

문제 링크입니다.

관찰

어떤 나무에서 날아갈 수 있는 모든 나무에 대해 피로도를 갱신하는 것은 비효율적입니다. 대신, 각 나무마다 그 나무로 날아올 수 있는 나무 중 최적인 것을 찾는 방법을 고민해 봅시다.

k개의 나무가 있으면, 그중 어떤 나무에서 날아오는 게 더 유리할지를 생각해봅시다. 가장 먼저, 반드시 고려해야 할 조건으로 그 나무에 도달할 때 느끼는 최소 피로도가 있습니다. 만약 어떤 나무에서 피로도가 다른 나무들보다 낮다면, 그 나무의 높이와 상관없이 그 나무에서 출발하는 게 무조건 이득입니다. 피로도는 해봤자 1 느는데, 그래도 구간 안의 다른 나무들에서 날았을 때의 피로도와 같거나 더 작을 테니까요.

만약 피로도가 같다면, 높은 나무에서 출발하는 쪽이 피로도를 덜 느낄 가능성이 높으므로 더 유리합니다.

단조성 유지하기

관찰한 내용을 바탕으로, 구간 안에서 날아봄직한 나무들만 남기는 방법을 생각해 봅시다. 이는 거꾸로 무슨 일이 있어도 이 나무에서 날아가는 경우를 고려해야 될 필요가 없는 나무를 뽑아내는 것으로 생각할 수 있습니다. 이는 자신보다 오른쪽에 있고 필요한 피로도가 더 적은 나무가 존재하거나, 필요한 피로도는 같은데 높이가 더 높은 나무가 존재하는 경우가 해당됩니다.

구간에 새 나무가 추가될 때마다 남아있는 맨 오른쪽 나무와 비교해 뽑아내는 작업을 해주면, 궁극적으로 구간에 남은 나무들은 오른쪽으로 갈수록 단조적으로 불리해지는 양상을 띠게 됩니다. 즉 현재 구간의 맨 왼쪽 나무에서 나는 게 항상 최적이도록 구간 안의 나무를 조정하는 겁니다.

덱을 이용해 양쪽에서 나무를 넣거나 뺄 수 있도록 해 줍시다. 거리가 k를 초과하게 된 나무는 앞에서 뽑아버리고, 새로 추가될 나무보다 불리한 나무는 뒤에서 뽑으면 됩니다.

이러면 쿼리 당 $\mathcal{O}(N)$의 시간 복잡도에 문제를 해결할 수 있습니다.

코드

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

struct t{
	int val, h, idx;
};

int n, k, q, a[1234567];
deque<t> dq;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n; for(int i = 0; i < n; i++) cin >> a[i];
  cin >> q; while(q--){
	dq.clear();
		cin >> k;
		dq.push_back({0, a[0], 0});
	for(int i = 1; i < n; i++){
			while(dq.size() && dq.front().idx + k < i) dq.pop_front();
			int now = dq.front().val + (bool)(dq.front().h <= a[i]);
			while(dq.size() && (dq.back().val > now || dq.back().val == now && dq.back().h <= a[i])) dq.pop_back();
			dq.push_back({now, a[i], i});
		}
		cout << dq.back().val << '\n';
	}
}