백준 6198 : 옥상 정원 c++ (monotone stack)

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

 

monotone stack이란?

-> 스택 내부를 오름차순 또는 내림차순으로 유지 해주는 알고리즘

https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack

풀이

1. 총합을 구하는 것이기 때문에 한 건물 한건물을 추가할때마다 stack 에 자기보다 큰놈들만 냅두기

-> 여기서 monotone  stack 사용

 

2. 자기보다 큰놈들 = 자기를 바라볼 수 있는 애들

 -> 매번 남은 stack의 사이즈를 정답에 더해주면 된다.

 

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

long long answer = 0;
int input;
stack<int> s;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input;

		while (!s.empty())
		{
			if (s.top() > input)
				break;

			s.pop();
		}

		answer += (long long)s.size();
		s.push(input);
	}


	cout << answer << endl;
	return 0;
}