[BOJ 2867] 수열의 값

2867번: 수열의 값

 

결국 백준에 손을 댔다(....) 그룹의 채점 현황을 구경하다가 이 문제를 보았는데, 풀이가 쉽게 생각나서 풀 수밖에 없었다..

 

나름 교육적인 문제이니 한 번 풀어보자.

 

$N$이 크기 때문에 $O(NlogN)$ 이상의 풀이를 생각해내야 한다. 이런 류의 문제는 주로 슬라이딩 윈도우 또는 세그먼트 트리를 이용하는데, 태그를 보면(?) 스택이라 하니 $O(N)$에 풀릴 거라고 추측할 수 있다. 이제 $i$번째 원소를 끝으로 하는 부분 수열의 값의 합을 $O(1)$에 구하는 것을 목적으로 해보자.

 

$ sum_{i}=\sum_{1\leq j\leq i}^{}val[a_{j},a_{j+1},\cdots,a_{i}] $ 을 $ O(1) $에 구하자. 누적합을 이용해야 될 것처럼 보이는데, 각 수열에서의 최대, 최소를 함께 생각하기가 힘들다. 하지만 $ sum_{i}=\sum_{1\leq j\leq i}^{}max[a_{j},a_{j+1},\cdots,a_{i}]-\sum_{1\leq j\leq i}^{}min[a_{j},a_{j+1},\cdots,a_{i}] $ 이기 때문에 최대, 최소를 따로 관리해줄 수 있다. 최솟값의 경향성을 생각해보면 단조 감소 수열을 이룬다는 것을 쉽게 알 수 있고, 최댓값도 마찬가지로 단조 증가수열을 이룰 것이다. 그렇다면 기존의 $[a_{1},\cdots,a_{i-1}]$에서 $a_{i}$가 추가될 때 뒤에서부터 연속한 부분이 변화함을 관찰할 수 있다. 이를 스택과 DP를 이용하면 스택과 누적합의 갱신을 $ O(N/N+1) $에 해결할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node { ll val,idx; };
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n; cin >> n;
	vector<ll> sn(n+1),sx(n+1);
	ll x,ans=0;
	stack<node> stn,stx;
	stn.push({0,0}); stx.push({(ll)1e9+1,0});
	for(int i=1;i<=n;i++){
		cin >> x;
		while(stn.top().val>x) stn.pop();
		while(stx.top().val<x) stx.pop();
		sn[i]=sn[stn.top().idx]+(i-stn.top().idx)*x;
		sx[i]=sx[stx.top().idx]+(i-stx.top().idx)*x;
		ans+=sx[i]-sn[i];
		stn.push({x,i}); stx.push({x,i});
	}
	cout << ans;
}

 

이번 글을 쓰면서 수식입력기의 필요성을 느꼈다. 시험 끝나고 배워보자.

+ 21.07.17 추가 : 수식입력기를 이용해서 풀이를 전면 수정했다.