[백준] 6198번 옥상 정원 꾸미기 (stack, c++)

스택에는 현재 인덱스 i를 집어넣는다.

그 전에 스택이 비어있지 않으면 스택의 최상단(위치 prev)과 현재 높이(위치 i)의 차이 -1(자기자신은 빼줌)

개수 만큼의 빌딩을 볼 수 있다는 이야기이다.

 

n=80000이고 자기 위치 다음 빌딩들이 모두 자기보다 작다하면 80000+ 79999 + 79998 +... 이런 예시가 들어온다

대략 n^2으로 계산하면 6.4*10^9 으로 int 범위가 넘어가므로 ans는 long long 형으로 해준다.

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int n;

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
    
		cin >> n;
		vector<int> v(n);
		long long sum = 0;
		stack<int> s;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		for (int i = 0; i < n; i++) {
			while (!s.empty() && v[s.top()]<=v[i]) {
				int prev = s.top();
				s.pop();
				sum+= i - prev - 1;
			}
			s.push(i);
		}
		while (!s.empty()) {
			int prev = s.top();
			s.pop();
			sum += n - prev - 1;
		}
		
		cout << sum;

	return 0;
}