백준 6549번 히스토그램에서 가장 큰 직사각형 (C++)

오늘은 오랫동안 묵혀두었던 P5 문제이다.

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제이다.

아이디어가 하나 떠오르자마자 바로 풀려서 생각보다 놀랐다.

오늘은 운수 좋은 날...?

문제링크

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

설명

일단 나는 이 문제를 스택으로 풀었다.

이 문제의 포인트는 어떠한 구간에서 최솟값이 넓이를 결정한다는 것과 자신의 index를 기준으로 좌우를 모두 생각해야 한다는 것이다.

예를 들어 index = 1, value = 4의 수가 있다고 가정하겠다.

또한 2가지 배열을 만들어 줄건데,
rans배열은 자신보다 더 큰 index를 가진 수들만 고려한 넓이이고
lans 배열은 자신보다 더 작은 index를 가진 수들만 고려한 넓이이다.

우선 rans배열을 보자.

위 정보를 스택에 넣어놓고 자신보다 큰 index를 가지는 수들 중, 더 작은 value를 가진 수가 들어올 때까지 for문을 돌린다.

자신보다 작은 value를 가진 값이 들어온다면 (index = 5, value = 3이라고 하자), rans[1]에 4 * (5 - 1)의 값인 16을 저장한다.

rans[3] = 16이 되는 이유는 index = 2, 3, 4일 때는 자신보다 더 큰 수가 들어와 높이가 4인 직사각형의 크기를 늘릴 수 있지만, index = 5일 때는 자신보다 작은 수가 들어와 높이가 4인 직사각형을 만들 수 없기 때문이다.

위 과정에 따르면
rans배열의 값은 index 순서대로 16 5 8 6 3이 될 것이다.

이제 lans배열을 생각해보자.

위 과정을 반대로 생각하면 된다.

위 그림에서 index = 5, value = 3인 수는 왼쪽으로 가면 넓이 15인 직사각형을 만들 수 있지만 rans배열에서는 자신보다 큰 index를 가진 수들만 고려하므로 3의 값을 가진다.

lans배열에는 자신보다 index가 작은 수들을 가지고 만들 수 있는 가장 큰 직사각형의 넓이를 저장한다.

위 그림으로 따지면 lans[5] = 15가 되고 lans[1] = 4가 된다.

이제 두 배열을 합쳐서 고려하면 된다.

rans배열과 lans배열을 합친 값에서 자기 자신의 값을 뺀 값들 중 가장 큰 수가 위 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이가 된다.

이를 식으로 나타내면 다음과 같다.

ans[i] = rans[i] + lans[i] - arr[i];
// rans[i] += lans[i] - arr[i];로 하면 메모리를 조금이라도 아낄 수 있다.

똑같은 내용이지만 수의 범위가 작은 다른 문제가 있다.

한 구간의 최솟값이 중요하다고 생각해서 맨 처음 세그먼트 트리를 이용하려다가 아이디어 적용에 실패해서 스택을 이용하는 아이디어로 문제를 풀었는데 다음에는 세그먼트 트리를 이용해서 그 문제를 풀어봐야겠다.

코드

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

using namespace std;

struct node {
	long long val;
	int idx;
};

int n;
long long arr[100000], rans[100000], lans[100000], ans[100000];

void input()
{
	for (int i = 0; i < n; i++)
		cin >> arr[i];
}

void rsol()
{
	stack<node> s;

	for (int i = 0; i < n; i++)
	{
		while (!s.empty() && s.top().val > arr[i])
		{
			long long val = s.top().val;
			int idx = s.top().idx;

			rans[idx] = (i - idx) * val;
			s.pop();
			continue;
		}

		s.push({ arr[i], i });
	}

	int midx = s.top().idx + 1;

	while (!s.empty())
	{
		long long val = s.top().val;
		int idx = s.top().idx;

		rans[idx] = (midx - idx) * val;
		s.pop();
	}
}

void lsol()
{
	stack<node> s;

	for (int i = n - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top().val > arr[i])
		{
			long long val = s.top().val;
			int idx = s.top().idx;

			lans[idx] = (idx - i) * val;
			s.pop();
			continue;
		}

		s.push({ arr[i], i });
	}

	int midx = s.top().idx - 1;

	while (!s.empty())
	{
		long long val = s.top().val;
		int idx = s.top().idx;

		lans[idx] = (idx - midx) * val;
		s.pop();
	}
}

void solution()
{
	rsol();       // 자기보다 큰 idx만 고려할 때
	lsol();       // 자기보다 작은 idx만 고려할 때

	for (int i = 0; i < n; i++)
		ans[i] = lans[i] + rans[i] - arr[i];

	cout << *max_element(ans, ans + n) << '\n';
}

void solve()
{
	while (1)
	{
		cin >> n;

		if (n == 0)
			break;

		input();
		solution();
	}
}

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

	solve();
	return 0;
}