히스토그램 내부 직사각형의 최대 넓이 [세그먼트 트리, 재귀]

1. 문제 정보

BOJ 1725 - 히스토그램 Platinum 5

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

 

2. 풀이

이 문제는 스택 알고리즘의 어려운 예제급 문제입니다.

그만큼 매우 유명하고 잘 알려져 있는데요.

 

하지만 스택을 이용한 풀이는 효율적이긴 하나 직관적으로 이해하기 어렵습니다.

저도 이 문제를 풀 때 스택보다 재귀를 이용해 풀었으며, 풀이도 더 이해가 잘 되고 직관적입니다.

 

k번째 막대를 살펴보고 있다고 할 때, 이 막대를 기준으로 생각해 볼 수 있는 경우는 아래 세 가지 경우입니다.

1. k번째 막대를 포함한 히스토그램 내부의 최대 직사각형 넓이

2. k번째 막대 왼쪽 히스토그램 내부의 최대 직사각형 넓이

3. k번째 막대 오른쪽 히스토그램 내부의 최대 직사각형 넓이

 

각 경우를 그림으로 살펴봅시다.

 

1. k번째 막대를 포함한 히스토그램 내부의 최대 직사각형 넓이

2. k번째 막대 왼쪽 히스토그램 내부의 최대 직사각형 넓이

3. k번째 막대 오른쪽 히스토그램 내부의 최대 직사각형 넓이

 

이 그림을 보면 이런 의문이 들 것입니다. "그러면 어떤 막대를 매번 골라야 하지?"

k번째 막대를 기준으로 좌우에 위치한 히스토그램을 살펴볼 때, k번째 막대는 포함되면 안 됩니다.

이 말은 즉 k번째 막대의 막대가 가장 높이가 낮다는 의미와 같고, 이는 곧 매번 가장 낮은 막대를 골라야 한다는 것과 같습니다.

 

처음에는 모든 범위를 보고 가장 낮은 막대 k를 고릅니다. 

범위가 [s, e]이고, k의 높이가 h라면 k번째 막대를 포함한 히스토그램 내부 최대 직사각형의 넓이는 h * (e - s + 1)입니다.

 

그 후 k번째 막대의 좌우 히스토그램, [s, k - 1], [k + 1, e] 범위의 히스토그램에 대해서도 같은 작업을 재귀적으로 반복해주면 됩니다.

 

범위 내 높이가 가장 낮은 막대를 선택하는 것은 세그먼트 트리로 쉽게 할 수 있습니다.

여기서 추가적으로 고려해야 하는 것은 보통 최솟값을 반환하는 세그먼트 트리를 구성하지만, 이 문제에서는 최솟값과 그 막대의 위치를 함께 저장해야 한다는 것입니다.

 

최솟값은 히스토그램의 넓이를 계산할 때 쓰이고, 막대의 위치는 그 막대의 좌우로 범위를 재설정해야 하기 때문입니다.

 

막대의 개수를 n이라고 하면, 이 풀이의 시간 복잡도는 O(nlogn)입니다.

 

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int SIZE = 1e5 + 6;
const int INF = 0x7FFFFFFF;
typedef pair<ll, int> p;

int n;
ll ans = 0, h[SIZE];
p tree[444444];

// tree initialization
p init_tree(int s, int e, int node){
    if(s == e) return tree[node] = {h[s], s};
    
    int m = (s + e) >> 1;
    p l = init_tree(s, m, node * 2);
    p r = init_tree(m + 1, e, node * 2 + 1);
    
    if(l.first < r.first) return tree[node] = l;
    return tree[node] = r;
}

// find minimum value and its position
p get_min(int x, int y, int s, int e, int node){
    if(x <= s && e <= y) return tree[node];
    if(e < x || y < s) return {INF, INF};
    
    int m = (s + e) >> 1;
    p l = get_min(x, y, s, m, node * 2);
    p r = get_min(x, y, m + 1, e, node * 2 + 1);
    
    if(l.first < r.first) return l;
    return r;
}

// calculate maximum area of histogram
void dfs(int s, int e){
    // find stick that has a minimum height between given range
    p m = get_min(s, e, 0, n - 1, 1);
    
    // including minimum stick
    ans = max(ans, m.first * (e - s + 1));
    int mid = m.second;
    
    // reset range: left, right
    if(s <= mid - 1) dfs(s, mid - 1);
    if(mid + 1 <= e) dfs(mid + 1, e);
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
	
    cin >> n; for(int i = 0; i < n; i++) cin >> h[i];
	
    init_tree(0, n - 1, 1);
    dfs(0, n - 1);
	
    cout << ans;
    return 0;
}

 

높이 값과 위치를 트리에 함께 저장하기 위해 tree 변수의 타입을 pair<long long, int> 로 설정했습니다.

이외에는 전형적인 재귀, 세그먼트 트리 코드이므로 부연 설명은 하지 않겠습니다.

---

히스토그램 내부 최대 넓이 직사각형을 구하는 문제는 너무 잘 알려져 있기 때문에 알아차리기 힘들게 출제가 됩니다.

제가 취미로 개발 중인 알고리즘 문제 풀이 사이트에서도 비슷한 문제를 담고있으니 참고해보시길 바랍니다!

Q73. 이상한 테트리스 2 - 달맹저지

---

제 글이 많은 도움이 되었길 바라며,
긴 글 봐주셔서 감사합니다!
멋진 개발자가 되기 위해 더 열심히 달리겠습니다!
- 달맹 -