[백준] 2304번: 창고 다각형

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

2304번: 창고 다각형

 

일단 막대 정보를 배열에 저장한 뒤,

막대를 왼쪽부터 오른쪽으로 훑으며 top보다 막대가 긴 경우 스택1에 push 해준다(다각형의 왼쪽 영역)

그 다음 이번엔 막대를 오른쪽부터 왼쪽으로 훑으며 top보다 막대가 긴 경우 스택2에 push 해준다(다각형의 오른쪽 영역)

탐색이 끝난 후, 스택1과 스택2의 top 사이의 넓이를 계산해준 뒤(위의 예시에서는 가장 긴 막대가 하나라서 크게 의미가 없지만 가장 긴 막대가 여러개일 수도 있기 때문)

각각의 스택을 pop하며 왼쪽 영역과 오른쪽 영역의 넓이를 계산해주면 끝

 

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int arr[1001] = { 0, };
	int result = 0;
	int left = 1000, right = 0;
	stack<int> st1, st2;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int l, h;
		cin >> l >> h;
		left = min(l, left);
		right = max(l, right);
		arr[l] = h;
	}

	st1.push(left);
	for (int i = left + 1; i <= right; i++) {
		if (arr[i] > arr[st1.top()]) st1.push(i);
	}

	st2.push(right);
	for (int i = right - 1; i >= left; i--) {
		if (arr[i] > arr[st2.top()]) st2.push(i);
	}

	// 가장 높은 막대 사이 거리
	result += (st2.top() - st1.top() + 1) * arr[st1.top()];

	// 왼쪽 영역
	int prev = st1.top();
	st1.pop();
	while (!st1.empty()) {
		result += (prev - st1.top()) * arr[st1.top()];

		prev = st1.top();
		st1.pop();
	}

	// 오른쪽 영역
	prev = st2.top();
	st2.pop();
	while (!st2.empty()) {
		result += (st2.top() - prev) * arr[st2.top()];

		prev = st2.top();
		st2.pop();
	}

	cout << result;
}