[백준/BOJ] 백준 6198번 : 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

스택을 이용하여 문제를 해결했다. 각 번호의(0번부터 시작) 빌딩에서 볼 수 있는 옥상의 개수를 저장하는 배열을 만들었다.

 

코드

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

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	long long input;
	vector<long long> building;
	stack<pair<long long,int>> s;
	long long result = 0;
	int can_see[80000]; //각 번호의(0번부터 시작) 빌딩에서 볼 수 있는 옥상의 개수 

	memset(can_see, 0, sizeof(can_see));

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		building.push_back(input);
	}

	for (int i = n-1; i >= 0; i--)
	{
		//가장 오른쪽 빌딩일때
		if (s.empty())
		{
			can_see[i] = 0;
			s.push(make_pair(building[i],i));
		}

		//볼 수 있는 옥상이 없을때
		else if (building[i] <= s.top().first)
		{
			can_see[i] = 0;
			s.push(make_pair(building[i], i));
		}

		//볼 수 있는 옥상이 있을때
		else if (building[i] > s.top().first)
		{
			int cnt = 0;
			while (!s.empty() && building[i] > s.top().first)
			{
				cnt += can_see[s.top().second];
				cnt++;
				s.pop();
			}

			can_see[i] = cnt;
			s.push(make_pair(building[i], i));

			result += cnt;
		}
	}

	cout << result;

	return 0;
}