[BOJ] 6549 - 히스토그램에서 가장 큰 사각형

[백준] 6549 - 히스토그램에서 가장 큰 사각형

접근

두 가지 풀이법이 있다. 첫째는 스택을 이용한 풀이법, 둘째는 세그먼트 트리를 이용한 풀이법이다.
나는 스택을 사용해 풀었다.

스택을 사용한 경우

쉽게 표현하자면, ‘현재 위치에서 얼마나 갈 수 있는지’를 따지는 것이다. 예를들어 현재 높이에서 오른쪽으로 당긴다고 하면, 오른쪽으로 한 칸씩 이동하며 건물 높이를 확인하다가 현재 높이보다 낮은 건물이 등장했을 때 마지막 지점으로 기록하는 것이다. 따라서 항상 스택에는 현재 위치보다 큰 건물만 남아있어야 한다. 여기서 조심할 것은, 한 번 배열을 돌 때 알 수 있는 것은 ‘현재 건물에서 해당 방향으로 얼마나 갈 수 있는지’라는 것이다. 따라서 오른쪽, 왼쪽 두 번을 확인해야 정확한 정답을 알아낼 수 있다.

추가 기재사항

나는 위의 주의사항을 처음에 이해하지 못해 한 번 스택을 돌 때 최댓값이 바로 나온다고 생각했는데, 이렇게 하면 양쪽으로 뻗어야 알 수 있는 경우를 걸러내지 못했다. 따라서 스택을 돌면서 바로 넓이를 계산하면 안되고 각각의 과정을 통해 나온 끝점을 이용해 넓이를 계산해야 한다.

소스코드

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <float.h>
#include <stack>
#define INF 987654321
using namespace std;
typedef long long ll;

ll square[100005], L[100005], R[100005];
stack<ll> s;

int main(void) {
	while (true) {
		ll n, ans = 0;
		scanf("%lld", &n);
		if (!n) break;
		for (ll i = 0; i < n; i++) {
			scanf("%lld", square + i);
		}

		for (ll i = 0; i < n; i++) {
			while (!s.empty() && square[s.top()] > square[i]) {
				R[s.top()] = i;
				s.pop();
			}
			s.push(i);
		}
		while (!s.empty()) {
			R[s.top()] = n;
			s.pop();
		}
		for (ll i = n - 1; i >= 0; i--) {
			while (!s.empty() && square[s.top()] > square[i]) {
				L[s.top()] = i;
				s.pop();
			}
			s.push(i);
		}
		while (!s.empty()) {
			L[s.top()] = -1;
			s.pop();
		}
		for (ll i = 0; i < n; i++) {
			ans = max(ans, (R[i] - L[i] - 1) * square[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

세그먼트 트리를 이용하는 경우

정확히 풀어보지 않았지만, 이론으로는 높이의 최솟값과 최댓값을 잡고 각 높이일 때의 넓이를 구한다. 세그먼트 트리를 통해 해당 구간에서 최소높이와 그 건물의 인덱스를 가져온다. 가져온 정보를 통해 구간을 나누고 넓이를 구하면 된다..! 약간 희미하게 이해한 것 같다.