[C++] 백준 6198번: 옥상 정원 꾸미기

문제 링크

6198번: 옥상 정원 꾸미기

문제 요약

N개의 빌딩이 있고 각 빌딩의 옥상에는 관리인이 있다. 관리인들은 오른쪽만을 보고 있으며, 자신이 보고 있는 건물보다 높이가 높거나 같은 빌딩이 있으면 그 다음 건물부터는 보지 못한다. 각 건물의 관리인들이 볼 수 있는 건물 수의 합을 구해야 한다.

접근 방법

하나의 스택을 준비하고, 건물을 순서대로 입력을 받습니다.

1. 만약 스택이 비었다면 현재 건물을 삽입하고 넘어갑니다.
2. 만약 비어있지 않다면 스택의 top과 높이를 비교합니다. top이 더 크다면 현재 스택의 사이즈만큼 정답을 증가시키고 삽입합니다.
3. 그렇지 않다면 top이 커질거나 스택이 빌 때까지 pop을 합니다. 그리고 스택의 사이즈만큼 정답을 증가시키고 삽입합니다.

간단한 스택 문제였습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	long long ans = 0;
	vector<int> v;
	for (int i = 0; i < n; i++)
	{
		int h;
		cin >> h;

		if (v.empty())
		{
			v.push_back(h);
			continue;
		}

		if (v.back() > h)
		{
			ans += v.size();
			v.push_back(h);
		}
		else
		{
			while (!v.empty() && v.back() <= h)
				v.pop_back();
			ans += v.size();
			v.push_back(h);
		}
	}

	cout << ans;
	return 0;
}