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

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리(Segment Tree) :: http://www.crocus.co.kr/648

세그먼트 트리를 이용하여 O(nlgn)에 해결 할 수 있는 문제이다.

이 문제를 이렇게 접할 수 있다는 것을 배우고 나서 매우 신기하였고, 세그먼트 트리를 배운 입장에서 응용 단계에는 아직 많이 못 미치는듯 하다.

init과정에서는 아래와 같이 세그먼트 트리의 리프 노드에는 인덱스 번호를, 그리고 그 위의 노드 부터는 그 구간에 해당하는 최소 높이에 해당하는 인덱스를 넣어준다.

(아래 댓글을 통해 수정하였습니다. 아래 그림상에서 리프노드가 아닌곳에 최소 높이가 다 적혀있는데 그게 아닌 최소 높이가 있는 인덱스가 있어야 합니다.)

그다음 아래와 같이 붉은색 내용 중 최소를 찾는 과정이 query 과정이고,

그 최솟값을 이용하여 start(s)와 end(e)를 이용하여 넓이를 구하는 과정이 getMax 과정이다.

세그 트리를 공부하고 스택이 아닌 세그 트리로 접근해보면 매우 흥미로운 문제인 것 같다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
void init(vector<int> &arr, vector<int> &tree, int node, int start, int end)
{
    // start와 end가 같으면 리프 노드. 이때 node에 start idx를 넣는다.
    if (start == end)
        tree[node] = start; 
 
    // start와 end가 다르다면
    else
    {
        int mid = (start + end) / 2;
        init(arr, tree, node * 2, start, mid);
        init(arr, tree, node * 2 + 1, mid + 1, end);
 
        // 각 구간에서 가장 높이가 낮은 것을 노드에 넣어준다.
        if (arr[tree[node * 2]] <= arr[tree[node * 2 + 1]])
            tree[node] = tree[node * 2];
        else
            tree[node] = tree[node * 2 + 1];
    }
}
 
// 구간에서 가장 최소인 높이의 막대 구하기
int query(vector<int> &arr, vector<int> &tree, int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return -1;
 
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
    int m1 = query(arr, tree, node * 2, start, mid, left, right);
    int m2 = query(arr, tree, node * 2 + 1, mid + 1, end, left, right);
 
    if (m1 == -1)
        return m2;
 
    else if (m2 == -1)
        return m1;
 
    else
    {
        if (arr[m1] <= arr[m2])
            return m1;
        else
            return m2;
    }
}
 
ll getMax(vector<int> &arr, vector<int> &tree, int start, int end)
{
    int n = arr.size();
    int m = query(arr, tree, 1, 0, n - 1, start, end);
 
    // 넓이 계산
    ll area = (ll)(end - start + 1)*(ll)arr[m];
 
    // 왼쪽 막대가 존재하냐?
    if (start <= m - 1)
    {
        ll tmp = getMax(arr, tree, start, m - 1);
 
        if (area < tmp)
            area = tmp;
    }
 
    // 오른쪽 막대가 존재하나?
    if (m + 1 <= end)
    {
        ll tmp = getMax(arr, tree, m + 1, end);
        if (area < tmp)
            area = tmp;
    }
 
    // 최대 넓이 반환
    return area;
}
 
int main()
{
    while (1)
    {
        int n;
        scanf("%d", &n);
 
        if (n == 0)
            break;
 
        vector<int> arr(n);
 
        // 값을 입력 받는다.
        for (int i = 0; i < n; i++)
            scanf("%d", &arr[i]);
 
        // 세그 트리 크기를 구한다.
        int h = (int)(ceil(log2(n))+1e-9);
        int tree_size = (1 << (h + 1));
 
        vector<int> tree(tree_size);
 
        // 세그 트리 형성
        init(arr, tree, 1, 0, n - 1);
 
        printf("%lld\n", getMax(arr, tree, 0, n - 1));
    }
 
    return 0;
}