[백준 6549] 히스토그램에서 가장 큰 직사각형 (C++)

문제 링크: https://www.acmicpc.net/problem/6549

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

1. 주의할 점

- 분할정복 + 세그먼트 트리를 통해 해결한다

 

2. 구현

- 직사각형의 높이에 대한 정보를 Arr[] 배열에 담는다

- Tree[] 배열을 동적할당한다

- Init() 배열을 통해 Tree[] 배열에 최소 높이를 가지는 인덱스 번호를 저장한다

- findMinIdx() 함수를 통해 Left~Right까지의 Arr[] 배열에서 가장 낮은 높이를 갖는 인덱스를 반환한다. 이때, 범위가 Start와 End의 사이가 아니라면 -1을 반환한다

- findMaxArea() 함수 내부에서는 findMinIdx() 함수를 통해 Left~Right사이에 위치한 가장 작은 높이를 가진 인덱스를 구한다. 이때, Temp에는 Arr[minIdx]*너비를 통해 현재 만들 수 있는 가장 큰 직사각형을 구하고 Result와 비교한다

- minIdx가 Left보다 오른쪽에 위치한다면, [Left,minIdx) 사이의 findMaxArea()를 수행한다

- minIdx가 Right보다 왼쪽에 위치한다면, (minIdx,Right] 사이의 findMaxArea()를 수행한다

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int *tree;
long long arr[100000];
long long result,curH;
int num;

int init(int node, int start, int end){
    if(start==end) return tree[node] = start;
    int mid = start + (end-start)/2;
    int lidx = init(2*node,start,mid);
    int ridx = init(2*node+1,mid+1,end);
    return tree[node] = arr[lidx] > arr[ridx] ? ridx : lidx;
}

int findMinIdx(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-start)/2;
    int lidx = findMinIdx(node*2, start, mid, left, right);
    int ridx = findMinIdx(node*2+1, mid+1, end, left, right);
    
    if(lidx==-1) return ridx;
    else if(ridx==-1) return lidx;
    return arr[lidx] > arr[ridx] ? ridx: lidx;
}

void findMaxArea(int left, int right){
    int minIdx = findMinIdx(1,0,num-1,left,right);
    long long temp = arr[minIdx]*(right-left+1);
    result = max(result,temp);
    if(left<minIdx)
        findMaxArea(left,minIdx-1);
    if(minIdx<right)
        findMaxArea(minIdx+1,right);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int height;
    while(1){
        cin>>num;
        if(num==0) break;
        height = ceil(log2(num));
        tree = new int[1<<(height+1)];
        //초기화
        for(int i=0;i<num;i++)
            cin>>arr[i];
        init(1,0,num-1);
        result=0;
        findMaxArea(0,num-1);
        cout<<result<<'\n';
    }
    return 0;
}