[백준] 2304번 창고 다각형

2304번: 창고 다각형

조건 중에 '오목한 부분이 없어야 한다'가 제일 중요하다.

오목한 부분이 없으려면 가장 긴 기둥을 기준으로

왼쪽이 계단식으로 올라가고

오른쪽은 계단식으로 내려가는 형태를 띄워야 한다.

 

값을 입력받으면서 시작 기둥과 끝 기둥,

그 사이에 있는 가장 긴 기둥들의 시작 위치와 끝 위치를 구한 뒤

결괏값에 가장 긴 기둥들의 넓이를 먼저 더해준다.

 

stack의 top < 현재 기둥

이 되면 한 단계 상승하는 것이므로

pop해주고 현재 기둥을 push해준 뒤

결괏값에 top을 더해준다.

이 외의 경우에는 그냥 결과값에 top만 더해준다.

 

이런 식으로 기준 기둥의 왼쪽과 오른쪽을 모두 구하여 더해주면 된다.

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
	int N;
	cin >> N;

	int storage[1001] = { 0 }, start = 11111, end = -1, a, b, Max = -1, idx1 = 0;
	for (int n = 0; n < N; n++) {
		cin >> a >> b;
		end = max(end, a);
		start = min(start, a);
		if (Max < b) { //기준 값인 가장 큰 기둥 찾기 위해
			Max = b;
			idx1 = a;
		}
		storage[a] = b;
	}

	int res = 0, idx2;
	for (int i = idx1; i <= end; i++) { //기준 기둥들 넓이
		if (storage[i] == Max) {
			idx2 = i;
			res += Max;
		}
	}

	stack <int> width;
	width.push(0);
	for (int i = start; i < idx1; i++) { //기준 기둥의 왼쪽 넓이
		if (width.top() < storage[i]) {
			width.pop();
			width.push(storage[i]);
		}
		res += width.top();
	}

	while (!width.empty()) width.pop();

	width.push(0);
	for (int i = end; i > idx2; i--) { //기준 기둥의 오른쪽 넓이
		if (width.top() < storage[i]) {
			width.pop();
			width.push(storage[i]);
		}
		res += width.top();
	}

	cout << res;

	return 0;
}