[백준6198] 옥상 정원 꾸미기 (C++)

📌 문제

BOJ 바로가기

스택 문제 은근 어렵다... ㅋㅋㅋㅋㅋ 😂
오큰수 문제, 탑 문제, Bad hair day 문제와 유사하다.

🗡 풀이

📍 현재 빌딩 (i)가 n이 될 때까지 반복문을 돌린다.

📍 만약 현재 빌딩이 이전 빌딩(스택에 쌓여있는 빌딩) 보다 크거나 같다면 이전 빌딩 입장에서 현재 빌딩 이후의 옥상을 전혀 보지 못한다. 따라서 이전 빌딩들을 pop한 후 ans를 스택 사이즈만큼 늘려준다.

🚩 소스코드

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, a[80001];
	long long ans = 0;
	stack<int> s;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		// 현재 빌딩이 크거나 같은 경우 pop
		while (!s.empty() && a[s.top()] <= a[i])
			s.pop();
		ans += s.size();
		s.push(i);
	}
	cout << ans;
}