백준 옥상 정원 꾸미기(6198) C++ 풀이

알고리즘 분류

자료 구조

스택

문제 해결 아이디어

뒤에 인덱스부터 탐색을 시작하여 Stack을 이용하여 현재 있는 곳에서 볼 수 있는 곳을 pop하면서
누적하여 저장하면 된다.

코드

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

struct Building
{
	long long height;
	long long cnt;
};

int n;
long long arr[80001];
stack<Building> st;
long long result = 0;

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0; i--)
	{
		long long count = 0;
		while (!st.empty())
		{
			if (st.top().height < arr[i])
			{
				count += st.top().cnt + 1;
				st.pop();
			}
			else
				break;
		}
		st.push({ arr[i], count });
		result += count;
	}

	cout << result;
}

 

코드 설명

높이와 볼 수 있는 개수를 저장 할 수 있는 구조체를 만들고 n - 1부터 탐색을 하여 top()의 높이보다 작으면 
top()에서 볼 수 있는 개수를 +1를 하여 계속 누적하여 계산 할 수 있도록 한다.