BOJ 6549 - 히스토그램에서 가장 큰 사각형 (세그트리, 분할정복, monotonic stack)

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

웰노운이지만 오늘에서야 이해한 문제.

참고: https://www.acmicpc.net/blog/view/12#comment-442

 

<문제설명>

히스토그램이 주어진다. 구간 [s,e] 넓이는 rmq(s,e)*(e-s+1)일 때, 최대 사각형의 넓이를 구해라.

 

<풀이1 분할정복>

rmq엔 구간 최소 높이를 갖는 '인덱스'를 저장한다.

 

구간 [s,e]에서 사각형의 최대 크기는 go(s,e)

1. 구간 최소 높이를 최대 높이로하는 사각형 h[rmq(s,e)]*(e-s+1)

2. 그 인덱스 좌측에서의 사각형 최대 크기 go(s,rmq(s,e)-1) 

3. 그 인덱스 우측에서의 사각형 최대 크기 go(rmq(s,e)+1,e)

go(s,e) = max(1,2,3)이다.

 

https://www.acmicpc.net/blog/view/12#comment-442

위 백준님의 자료를 보면, 인덱스 m을 기준으로 왼쪽 블럭에서 더이상 최대값을 갱신하지 못하고,

오른쪽블럭에서도 더이상 최대값을 갱신하지 못한다.

 

정답이 int범위를 넘어서는 경우 주의

 

<코드>

const int SMAX = (1<<18);
const int MAX = 1e5 + 5;

int a[MAX], seg[SMAX], n; //구간 a최소값 인덱스
int oper(int s, int e) {
	if (e == -1) return s;
	if (s == -1) return e;
	if (a[s] <= a[e]) return s;
	else return e;
}
void construct() {
	for (int i = SMAX / 2 - 1; i >= 1; i--) 
		seg[i] = oper(seg[i * 2], seg[i * 2 + 1]);
}
void seginit() {
	memset(seg, -1, sizeof(seg));
	for (int i = SMAX/2; i < SMAX/2+n; i++) 
		seg[i] = i-SMAX/2;
	construct();
}

int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return -1;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return oper(val(s, e, node * 2, ns, mid), val(s, e, node * 2 + 1, mid + 1, ne));
}
int val(int s, int e) {return val(s, e, 1, 0, SMAX / 2 - 1);}

ll go(int s, int e) {
	int mn = val(s, e);
	ll ret = (ll)a[mn] * (e - s + 1);
	if (s < mn) ret = max(ret, go(s, mn - 1));
	if (e > mn) ret = max(ret, go(mn + 1, e));
	return ret;
}

int main() {
	FAST;
	cin >> n; 
	for (int i = 0; i < n; i++) cin >> a[i];
	seginit();
	cout << go(0, n - 1) << '\n';	
}

 

---

<풀이 2 monotonic stack>

 

j번지점을 높이로 하는 사각형의 최대 넓이는 다음과 같이 구할 수 있다.

구간 [left, right]의 길이 * h[j]가 그 사각형이라고 할 때,

left   : h[j]보다 작고, 왼쪽으로 가장 가까운 높이를 갖는 인덱스+1 이다.

right : h[j]보다 작고, 왼쪽으로 가장 가까운 높이를 갖는 인덱스-1 이다.

 

monotonic stack에 h[i] 이하, 높이가 오름차순이 되도록 인덱스를 넣어둔다.

 

i=0~n-1까지 순회하면서 stack에 있는 요소가 pop될 때(h[i]보다 h[s.top()]이 클 때), pop된 인덱스를 j라고 하자.

left[j]는 s.top()+1이고, right[j] = i-1이다.

h[j]를 높이로하는 사각형의 최대 넓이는 (i-1-(s.top()+1)+1) * h[j]이다.

 

모두 순회하고, stack을 모두 비울 때까지 진행한다.

 

 

<코드>

int n, h[MAX];
int main() {
	FAST;
	while (true) {
		cin >> n; if (n == 0) break;
		for (int i = 0; i < n; i++) cin >> h[i];
		stack<int> s;
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			while (!s.empty() && h[s.top()] > h[i]) {
				int height = h[s.top()]; s.pop();
				int width = i;
				if (!s.empty()) width = (i - s.top() - 1);
				ans = max(ans, 1LL * width * height);
			}
			s.push(i);
		}
		while (!s.empty()){
			int height = h[s.top()]; s.pop();
			int width = n;
			if (!s.empty()) width = (n - s.top() - 1);
			ans = max(ans, 1LL * width * height);
		}
		cout << ans << '\n';
	}
}

 

 

<생각>

웰노운. 다른 문제에 적용할 수 있을 만큼 유념하자