BOJ 6549 히스토그램에서 가장 큰 직사각형

소마 코테 이후로 거의 8달 가까이 놓고있던 알고리즘 문제풀이를 다시 시작했다.

기억을 되살리기 위해서 템플릿을 보지 않고 기억에 의존해서 코드작성을 했는데, 생각보다 많은것을 아직 기억하고 있어서 다행이다.

 

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

6549번: 히스토그램에서 가장 큰 직사각형

 

이 문제는 사실 군복무 전인 2018년 쯤부터 알고 있던 문제였으나, 접근방법을 몰라서 손도 대지 않고 있던 문제였다.

이후에도 몇번씩 풀이를 생각해보았지만, 엄두를 내지 못했다.

이번에도 풀지 못하면 풀이를 확인하겠다는 다짐을 하고 다시 잡아보았다.

 

우선 문제 본문만 읽어보아도 세그트리라는것을 알 수 있다.

구간에서의 최소높이를 알고 있어야 해당 구간에서 그릴 수 있는 사각형의 넓이는 (끝지점 - 시작지점 + 1) * (구간의 최소높이) 라는 것을 알 수 있다.

 

그러면 이 구간을 어떻게 잡느냐인데.. 당연히 n^2으로 잡으면 터진다.

그러면 n logn으로 잡아야하는데 생각나는것은 분할정복이다.

 

분할정복의 기본적인 기법중 하나인,

왼쪽구간에서의 최적의 값 + 오른쪽구간에서의 최적의 값 + 양쪽을 합친 구간에서의 최적의 값

으로 접근을 시도 해보았다.

 

왼쪽/오른쪽은 어찌어찌 된다고 하더라도, 양쪽을 합친 구간의 최적의 값을 구하는 방법이 도저히 떠오르지 않았다.

그래서.. 이번에도 못풀었으니 나중에도 못풀것이라고 생각하고 구글링을 해보았다.

 

그런데,, 처음 들어간 블로그의 첫 문단에 이런 말이 있었다.

"구간에서의 최소높이를 기준으로 좌/우로 분할정복을 하면 된다"

 

이 문구를 보고 탄성을 질렀다.

해당 구간에서 최소높이인 블록을 포함하지 않는 구간을 살펴보아야 최대넓이를 찾을 수 있다는 당연한 사실조차도 생각하지 못하고 있었던 것이다.

 

그래서 바로 해당 아이디어를 코드로 옮겼고, 맞았다.

 

세그트리 구성과 트리에서 찾는 함수, 분할정복하는 함수를 기억대로 작성해서 살짝 더럽다.

특히 세그트리를 구성할 때, 리프노드에는 각 위치에 해당하는 높이를 저장했으나, 그 외의 노드에는 해당 구간에서 최소높이를 가지는 인덱스를 저장하도록 해서, 이것때문에 본인조차 헷갈려서 틀렸습니다를 맞았다;;

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
vector<int> height;
vector<int> seg;
ll ans;
int n, k;

//fs, fe : 찾으려는 구간의 시작/끝 위치
//idx : 현재 보고있는 노드의 인덱스
//ns, ne: 현재 보고있는 노드가 담당하는 구간
ii find(int fs, int fe, int idx, int ns, int ne) {
	
    //구간에서 벗어난경우
    if (ne < fs || fe < ns) return ii(2147483647, -1);
    
    //구간에 완전히 포함되는경우
	if (fs <= ns && ne <= fe) {
    	
        //세그트리를 더럽게 짜서.. 리프노드와 그 외 노드에 들어가는 값이 달라서 사용한 if문
		if (ns == ne) {
			return ii(seg[idx], idx);
		}
		return ii(seg[seg[idx]], seg[idx]);
	}
	ii t1, t2;
	t1 = find(fs, fe, idx * 2, ns, (ns + ne) / 2);
	t2 = find(fs, fe, idx * 2 + 1, (ns + ne) / 2 + 1, ne);
    
    //좌/우 구간을 확인해서, 더 낮은 높이를 return해주어야 한다.
	if (t1.first < t2.first) {
		return t1;
	}
	else return t2;
}

//s부터 e까지의 구간을 분할정복 하는 함수
void func(int s, int e) {

	if (e < s) return;
    
    //구간 1짜리 예외처리
	if (s == e) {
		ans = max(ans, (ll)height[s-1]);
		return;
	}
    
    //해당 구간에서의 최소높이를 찾아준다.
	ii f = find(s, e, 1, 1, k / 2);
    
    //해당 구간에서 그릴 수 있는 사각형 넓이를 계산
	ans = max(ans, f.first * (ll)(e-s+1));
    
    //최소높이 위치를 기준으로 다시 분할정복
	func(s, f.second - 1 - k/2 + 1);
	func(f.second + 1 - k / 2 + 1, e);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while (1) {
    
    	//입력
		cin >> n;
		if (n == 0) break;
		ans = 0;
		height.resize(n);
		for (int i = 0; i < n; i++) {
			cin >> height[i];
		}
		
        //세그트리 구성
        k = 1;
		while (k < n) k *= 2;
		k *= 2;
		seg.resize(k);
		for (int i = k / 2; i < k/2+n; i++) {
			seg[i] = height[i - k / 2];
		}
		for (int i = k / 2 - 1; i > 0; i--) {
			if (i >= k / 4) {
				if (seg[i * 2] < seg[i * 2 + 1]) {
					seg[i] = i * 2;
				}
				else seg[i] = i * 2 + 1;
			}
			else {
				if (seg[seg[i * 2]] < seg[seg[i * 2 + 1]]) {
					seg[i] = seg[i * 2];
				}
				else seg[i] = seg[i * 2 + 1];
			}
		}
        
        //분할정복 시작
		func(1, n);
        
		cout << ans << "\n";
	}
	return 0;
}