BOJ [1725] 히스토그램

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

1. 분류

스택, 스위핑 알고리즘, 분할정복

2. 풀이

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

히스토그램을 이루는 막대의 개수와 각 막대의 길이를 입력으로 받는다.

막대기들의 높이는 입력받은 숫자이며 폭은 1로 고정되어 있다.

예제 입력이 최대 10만개까지인데, 100000의 제곱은 100억이므로 O(N^2)으로 풀면 시간초과가 날 것이다.

위의 분류에서 소개한 스위핑 알고리즘을 쉽게 설명하면 진행할 한 쪽 방향을 정하고 쓱 훑고 지나가며 값을 찾는 방법인데 이런 문제에 아주 적합하다.

그림으로 그리면 아래와 같다.

7개를 입력받았을 때 단 7번만 검사하므로 시간 복잡도는 O(N)이다.

입력의 최대값을 주어도 시간 초과가 나지 않을 것이다.

이 알고리즘을 구현하기 위해 스택이 필요하다.

위의 그림에서 파란 칸은 현재 스택에 들어간 막대를 나타낸다.

1. 맨 처음엔 아무 값도 없으니 첫 번째 막대의 높이를 스택에 넣는다.

2. 두 번째 막대가 첫 번째 막대보다 낮다. 스택에 들어있던 값을 빼내며 넓이를 계산하고 두 번째 막대의 높이를 넣는다.

3. 세 번째 막대가 두 번째 막대보다 크다. 스택에 넣는다.

4. 윗 단계와 같다.

5. 다섯 번째 막대가 네 번째 막대보다 작다. 다섯 번째 막대보다 작은 것을 전부 빼내며 넓이를 계산한다.

6. 마찬가지로 계속 진행한다.

7. 마지막 막대의 처리 역시 윗 단계들과 마찬가지이다. 마지막 막대까지 스택에 넣고 나면 남은 막대들을 모두 빼내며 넓이를 계산한다.

핵심은 스택에 들어있는 막대보다 다음의 막대가 크거나 같으면 그냥 스택에 넣고,

그게 아니라면 현재 들어있는 막대 중 다음에 넣을 막대보다 큰 막대들을 전부 빼내며 넓이를 계산한 후 스택에 넣는 것이다.

---

3. 소스코드

#include <cstdio>
#include <stack>
using namespace std;
typedef unsigned long long ull;
ull hist[100000];
stack<int> st;

int main()
{
	int n;

	ull max = 0ull;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &hist[i]);
		while (!st.empty() && hist[st.top()] > hist[i])
		{
			int j = st.top();
			st.pop();
			ull width = i;
			if (!st.empty())
				width -= st.top() + 1;
			ull cmp = hist[j] * width;
			max = max < cmp ? cmp : max;
		}
		st.push(i);
	}

	while (!st.empty())
	{
		int j = st.top();
		st.pop();
		ull width = n;
		if (!st.empty())
			width -= st.top() + 1;
		ull cmp = hist[j] * width;
		max = max < cmp ? cmp : max;
	}

	printf("%llu\n", max);

	return 0;
}