백준 6549번: 히스토그램에서 가장 큰 직사각형 (플래티넘 V)

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

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

 

 

 

이런 식으로 히스토그램이 주어졌을 때, 

만들 수 있는 가장 큰 직사각형의 넓이를 구하면 된다고 한다.

 

사실 이 문제는 동치인 문제가 굉장히 많아서,

하나만 풀면 플래티넘 V 문제를 무려 6개 가량 해결해버릴 수 있는 솔브닥 점수 버핑 문제이다.

이 문제를 풀고 같은 유형의 문제로 복습해보기 좋다.

 

요즘 내 세그먼트 트리 폼이 올랐으므로, 한번 세그먼트 트리로 접근해보자.

 

---

Segment Tree & 분할 정복

 

우선 구간 전체를 지나는 직사각형의 최댓값은 어떻게 구할까?

바로 구간의 길이와 구간의 히스토그램 최솟값을 곱하는 것이다. 

 

L~R 구간을 차지하는 직사각형의 최댓값 = (R - L + 1) * (L~R 구간의 최솟값)

 

 

(6-0+1)*1 = 7 * 1 = 7

 

 

0~6까지의 구간(A라고 정의하겠다)에서 만들 수 있는 직사각형의 넓이는 7이다.

 

근데 이보다 큰 직사각형을 만들고 싶다면 어떻게 해야할까?

더 크게 직사각형을 만들고 싶지만 현재는 높이 1의 장벽에 갇혀있기 때문에 더 키울 수가 없다.

 

따라서 최솟값을 기준으로 구간을 나눠서 생각해보자.

최솟값 1을 기준으로 왼쪽편에서 가능한 직사각형(A.A라고 하자)과

오른쪽편(A.B라고 하자)에서 가능한 직사각형을 구한다.

 

최솟값 1의 인덱스가 1이므로,

0~0 구간(A.A)과 2~7 구간(A.B)에서의 직사각형 값을 구하면 된다.

 

 

1 * 2 vs 5 * 1

 

L~R 구간을 차지하는 직사각형의 최댓값 = (R - L + 1) * (L~R 구간의 최솟값)

 

이었으니까,

 

왼쪽편(A.A)의 직사각형 넓이는 (0 - 0 + 1) * 2 = 2이고,

오른쪽편(A.B)의 직사각형 넓이는 (6 - 2 + 1) * 1 = 5이다.

 

A.A는 더 이상 나눌 수 있는 여지가 없고,

나눌 수 있는 A.B은 또 똑같이 최솟값을 기준으로 분할하여 계산해본다.

 

2 * 4 vs 2 * 3

 

왼쪽편(A.B.a)에서는 8, 오른쪽편(A.B.b)에서는 6의 직사각형이 나온다.

설명이 길어지니 글은 접어놓도록 하자.

 

A.B.a를 또 분할해서

A.B.a.a(넓이 4), A.B.a.b(넓이 5)를 구한 후

드디어 분할하지 못하므로 백트래킹을 시작한다.

 

A.B.a.a(4)와 A.B.a.b(5), A.B.a(8)을 비교하면 8이 가장 크므로

A.B.a 구간의 가장 큰 직사각형 넓이는 8이고

 

A.B.b를 분할해서

A.B.b.a(넓이 3), A.B.b.b(넓이 3)를 구한 후

A.B.b.a(3)과 A.B.b.b(3), A.B.b(6)을 비교하면 6이 가장 크므로

A.B.b 구간의 가장 큰 직사각형 넓이는 6이고

 

A.B.a(8), A.B.b(6), A.B(5)를 비교하면 8이 가장 크므로

A.B 구간의 가장 큰 직사각형의 넓이는 8이고

 

A.B(8), A.A(2), A(7)를 비교하면 8이 가장 크므로

A 구간의 가장 큰 직사각형의 넓이는 8이 된다.

---

 

 

이런식으로 계속해서 분할 정복하는 방식으로 풀면 답을 구할 수 있다.

 

이렇게 풀려면, 구간의 최솟값과 그 인덱스를 빠르게 구할 수 있어야하는데,

구간의 최솟값이라.. 세그먼트 트리가 떠오르지 않는가?

 

세그먼트 트리에 구간의 최솟값 인덱스를 저장하여

빠르게 구간을 나눌 수 있도록 하자.

 

 

코드로 구현하면 다음과 같다.

 

// 히스토그램에서 가장 큰 직사각형
// 세그먼트 트리 & 분할 정복

// 구간의 최솟값을 저장한 이후
// 최솟값 * 구간을 사각형의 넓이로 산정하고
// 그 최솟값 왼편과 오른편 각각에 더 넓은 사각형이 있는지
// 분할정복으로 구함

#include <iostream>
#include <vector>
#include <cmath>

typedef long long ll;
const ll inf = 2000000000;

int N;
ll arr[100001];
std::vector<ll> minTree;
// minTree는 구간의 최솟값을 지닌 인덱스를 보관한다

ll makeTree(int node, int s, int e){
    if( s == e ){
        return minTree[node] = s;
    } else {
        int mid = (s+e)/2;
        int left = makeTree(node*2,s,mid);
        int right = makeTree(node*2+1,mid+1,e);
        if(arr[left] < arr[right]){
            return minTree[node] = left;
        } else {
            return minTree[node] = right;
        }
    }
}
ll search(int node, int s, int e, int l, int r){
    if(r < s || e < l){
        return inf;
    } else {
        if(l <= s && e <= r){
            return minTree[node];
        } else {
            int mid = (s+e)/2;
            int left = search(node*2,s,mid,l,r);
            int right = search(node*2+1,mid+1,e,l,r);
            if(left == inf){
                return right;
            } else if(right == inf){
                return left;
                // 위에 두 조건은 오류 방지용
            } else if(arr[left] < arr[right]){
                return left;
            } else {
                return right;
            }
        }
    }
}

ll solve(int s, int e){
    
    int minInd = search(1,0,N-1,s,e);

    ll height = (ll)(e-s+1);
    ll area = arr[minInd] * height;

    // minInd 기준 왼쪽에 더 큰 사각형이 존재하는지 판별
    if(s <= minInd - 1){
        ll tmp = solve(s, minInd-1);
        if(tmp > area){
            area = tmp;
        }
    }

    // minInd 기준 오른쪽에 더 큰 사각형이 존재하는지 판별
    if(e >= minInd + 1){
        ll tmp = solve(minInd+1,e);
        if(tmp > area){
            area = tmp;
        }
    }

    return area;
}

int main(){

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    arr[100000] = 1000000000;

    while(true){

        minTree.clear();

        std::cin >> N;

        if(N == 0){
            break;
        }

        for(int i = 0; i < N; i++){
            std::cin >> arr[i];
        }

        int height = (int)std::ceil(std::log2(N));
        int size = ( 1 << (height+1));
        minTree.resize(size);

        makeTree(1,0,N-1);


        std::cout << solve(0,N-1) << '\n';

    }


    return 0;
}