백준6198 옥상 정원 꾸미기

작성일 | In

문제 링크

  • http://icpc.me/6198

문제 출처

  • 2006 USACO November Silver 1번

사용 알고리즘

  • Monotone Stack

시간복잡도

  • O(N)

풀이

왼쪽에 있는 건물부터 하나씩 차례대로 보면서, 해당 건물을 볼 수 있는 건물의 개수를 구하는 방식으로 진행할 것입니다.

예제를 보면 10 3 7 4 12 2 와 같이 주어집니다.
첫 번째 건물의 높이는 10입니다. 가장 왼쪽에 있으므로 어떠한 건물도 이 건물을 볼 수 없습니다.
두 번째 건물의 높이는 3입니다. 첫 번째 건물이 이 건물을 볼 수 있습니다.
세 번째 건물의 높이는 7입니다. 첫 번째 건물이 이 건물을 볼 수 있습니다.
네 번째 건물의 높이는 4입니다. 첫 번째와 세 번째 건물이 이 건물을 볼 수 있습니다.
다섯 번째 건물의 높이는 12입니다. 어떠한 건물도 이 건물을 볼 수 없습니다.
여섯 번째 건물의 높이는 2입니다. 다섯 번째 건물이 이 건물을 볼 수 있습니다.

이 기법을 사용하면 위애 있는 정보들을 빠르게 구해낼 수 있습니다.
스택을 순 감소 상태로 유지를 하면서 각 건물을 처리해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

stack<int> s;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> v(n);
	for(int i=0; i<n; i++) cin >> v[i];

	ll ans = 0;
	for(int i=0; i<n; i++){
		while(!s.empty() && s.top() <= v[i]) s.pop();
		ans += (ll)s.size();
		s.push(v[i]);
	}
	cout << ans;
}