[백준] 2304번: 창고 다각형(스택을 이용한 최소 구획 정하기)

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

2304번: 창고 다각형

이전에 풀었던 주식 문제와 유사하되, 조금 더 어려운 문제이다.

왜냐하면 주식에서는 단편적으로 주식 가격을 파악하면 되었지만 이제는 기둥의 길이가 서로 영향을 주기 때문에 어렵다..

천막을 치는 패턴을 파악했어야 했는데, 여기서 나의 큰 실수가 있었다.

천막 높이의 갱신하는 점이 단순히 우상향인 줄 알았는데, 만약 우하향으로 되는 방식도 고려해야 한다.

 

이걸 어떻게 처리해야하나 고민했는데, 알아보니 굉장히 앞으로 유용할 것 같은 알고리즘이다.

기본적으로 Stack을 쓰면 훨씬 편하게 구현할 수 있다. 이를 통해 천막 높이의 변화가 생기는 기점을 기록할 수 있고, 또한 높이의 변화의 조건을 파악할 수 있다.

가장 높은 기둥을 기점으로 좌, 우로 분할하여 좌측에서는 우상향하는 기점을 스택에 저장하고, 우측에서는 우하향하는 기점을 다른 스택에 저장한다.

 

if(st_left.top().second < v[i].second) {
    st_left.push(v[i]);
}

점점 더 높은 천막을 짓는다고 전제하면, 낮은 기둥은 애초에 천막의 높이가 될 수 없기 때문이다.

 

+) 예외를 고려할 때 가장 높은 기둥이 다수인 경우도 고려해야한다.

 

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

int roof_area(stack<pair<int,int>> &st) {
	int area_sum = 0;
	pair<int,int> now_pillar, next_pillar;

	while(st.size() > 1) {
		now_pillar = st.top();
		st.pop();
		next_pillar = st.top();
		area_sum += abs(now_pillar.first - next_pillar.first) * next_pillar.second;
	}

	return area_sum;
}


int main() {

	cin >> N;
	vector<pair<int,int>> v;
	stack<pair<int,int>> st_left, st_right;

	int l, h, max_h = 0;
	for(int i = 0;i < N;i++) {
		cin >> l >> h;
		max_h = max(max_h, h);
		v.push_back({l, h});
	}

	sort(v.begin(), v.end());

	int left_end, right_end;
	for(int i = 0;i < N;i++) {
		if(v[i].second == max_h) {
			left_end = i;
			break;
		}
	}

	for(int i = N - 1;i >= 0;i--) {
		if(v[i].second == max_h) {
			right_end = i;
			break;
		}
	}

	if(right_end != N - 1) {
		st_right.push(v[N - 1]);
		// 중간에 위치한 가장 높은 기둥 우측과 오른쪽 끝 기둥들중 유의미한 기둥들만 push
		for(int i = N - 2;i > right_end;i--) {
			// 매우 유용한 기법이다..(끄적끄적)
			if(st_right.top().second < v[i].second) {
				st_right.push(v[i]);
			}
		}
		st_right.push(v[right_end]);
	}

	if(left_end != 0) {
		st_left.push(v[0]);
		for(int i = 1;i < left_end;i++){
			if(st_left.top().second < v[i].second) {
				st_left.push(v[i]);
			}
		}
		st_left.push(v[left_end]);
	}

	int area_sum = 0;
	area_sum += roof_area(st_left);
	area_sum += roof_area(st_right);
	// 가장 높은 기둥의 크기(동일한 위치의 기둥이 있는 경우도 함께 처리)
	area_sum += (v[right_end].first - v[left_end].first + 1) * v[right_end].second;

	cout << area_sum << '\n';
}