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

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

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

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!!

https://rudalsd.tistory.com/51?category=1073064 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

 

먼저 높이 값이 가장 작은 idx를 각각의 노드에 저장하는 세그먼트 트리를 만듭니다. 그 후 일정 구간에서 가장 작은 높이를 가지는 idx를 구하는 함수를 만든 후 그 idx를 기준으로 왼쪽 오른쪽으로 나누어 분할 정복을 해주시면 됩니다.

 

다음 글은 스택을 활용하여 문제를 푸는 방법입니다.

https://rudalsd.tistory.com/89?category=1064612 

 

[ 소스 코드 ]

 

#include<iostream>
#include<cmath>
 
#define ll long long
 
using namespace std;
 
int n;
int segTree[300000];
ll arr[100001];
ll ans;
 
int makeTree(int node, int start, int end)        //세그먼트 트리 만들기
{
    if (start == end) {        //리프노드
        return segTree[node] = start;
    }
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);        //왼쪽 자식 노드
    int right = makeTree(node * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
 
    return segTree[node] = arr[left] > arr[right] ? right : left;
}
 
int find(int node, int start, int end, int sidx, int eidx)    //최소 높이의 idx return
{
    if (eidx < start || sidx > end) return 0;    //범위에 완전히 포함되지 않을 때
    if (start >= sidx && end <= eidx) return segTree[node];    //범위에 완전히 포함될 때
    //범위에 일부 포함될 때
    int mid = (start + end) / 2;
    int left = find(node * 2, start, mid, sidx, eidx);
    int right = find(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left == 0) return right;
    if (right == 0) return left;
    return arr[left] > arr[right] ? right : left;
}
 
void getMax(int start, int end)
{
    if (start > end) return;
    int min = find(1, 1, n, start, end);
 
    ll W = arr[min] * (end - start + 1);
    ans = max(ans, W);
 
    getMax(start, min - 1);
    getMax(min + 1, end);
}
 
int main()
{
    while (1)
    {
        ans = 0;
        scanf("%d", &n);
        if (n == 0)break;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &arr[i]);
        }
 
        makeTree(1, 1, n);
 
        getMax(1, n);
 
        printf("%lld\n", ans);
    }
}