[BOJ 1725] 히스토그램

[BOJ 1725] 히스토그램 - P5

문제 요약

히스토그램에서 만들 수 있는 직사각형 중에서 가장 큰 넓이를 찾는 문제이다.

문제 풀이

직사각형의 넓이는 (r - l + 1) * getMin(l,r) 로 구할 수 있다. 여기서 문제는 N = 10만이므로 l,r을 전탐색으로 돌리면 시간이 초과하게 된다.
해결 방법은 세그먼트 트리에 가장 작은 값의 인덱스를 저장해놓는 것이다. 그래서 퀵소트가 작동하는 방식처럼 매 [l,r]구간에서 가장 작은 값의 인덱스를 찾아서 넓이를 구한 다음, 그 인덱스를 기준으로 좌, 우를 갈라서 똑같이 재귀적으로 넓이를 구해주면 된다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int SIZE = 100009;
const int INF_IDX = 0;
int tree[SIZE*8],h[SIZE];
int startIdx = 1;

int makeTree(int node){
    if(node >= startIdx) return tree[node];
    int lChild = node*2, rChild = node*2+1;

    if(h[makeTree(lChild)] > h[makeTree(rChild)]) tree[node] = tree[rChild];
    else tree[node] = tree[lChild];

    return tree[node];    
}

int getSmallestIdx(int node,int cl,int cr,int ql,int qr){
    if(ql > cr || cl > qr) return INF_IDX;
    if(qr >= cr && ql <= cl) return tree[node];

    int mid = (cl+cr)/2;
    int leftIdx = getSmallestIdx(node*2,cl,mid,ql,qr),
        rightIdx = getSmallestIdx(node*2+1,mid+1,cr,ql,qr);

    if(h[leftIdx] > h[rightIdx]) return rightIdx;
    else return leftIdx;
}

ll getMaxArea(int l,int r){
    if(l > r) return 0;

    int curIdx = getSmallestIdx(1,1,startIdx,l,r);
    ll curArea = 1LL * h[curIdx] * (r - l + 1);

    ll leftArea = getMaxArea(l, curIdx - 1), rightArea = getMaxArea(curIdx + 1, r);

    return max({curArea,leftArea,rightArea});
}

int main(){
    int n;  scanf("%d",&n);
    tree[0] = 0;
    h[INF_IDX] = 2e9;

    for(;startIdx < n ; startIdx *= 2);
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&h[i]);
        tree[startIdx + i -1] = i;
    }
    makeTree(1);

    printf("%lld\n",getMaxArea(1,n));
    return 0;
}