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

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

아이디어

분할정복 문제다. 전체 구간을 start ~ end라 하자. 이중에서 높이가 최소인 막대기의 인덱스를 i라 하면 높이가 arr[i]인 직사각형의 최대 넓이는 (end-start+1)*arr[i]가 된다.
그리고 인덱스 i를 기준으로 양 옆으로 나누면, 거기에는 무조건 arr[i] 이상의 높이를 가진 i가 존재할 것이다.
구간을 start ~ i-1, i+1 ~ end로 잡고, 또다시 그 구간에서 높이가 최소인 인덱스를 찾고, 직사각형의 최대 넓이를 구하는 것을 반복한다.
구간이 주어졌을 때 최소의 높이를 가지는 인덱스는 세그먼트 트리로 로그 시간에 찾을 수 있다.

요런 느낌으로다가..

코드

#include <bits/stdc++.h>

using namespace std;

int N = 1;
vector<int> arr, tree;

int init(int start, int end, int node) {
    if (start == end) {
        return tree[node] = start;
    }
    int ret1 = init(start, (start+end)/2, node*2);
    int ret2 = init((start+end)/2+1, end, node*2+1);
    if (arr[ret1] < arr[ret2]) return tree[node] =  ret1;
    else return tree[node] = ret2;
}

int get_min_idx(int start, int end, int left, int right, int node) {
    if (start > right || end < left) return -1;
    else if (left <= start && end <= right) return tree[node];
    int ret1 = get_min_idx(start, (start+end)/2, left, right, node*2);
    int ret2 = get_min_idx((start+end)/2+1, end, left, right, node*2+1);
    if (ret1 == -1) return ret2;
    if (ret2 == -1) return ret1;
    if (arr[ret1] < arr[ret2]) return ret1;
    else return ret2;
}

long long solve(int start, int end) {
    if (start == end) return arr[start];
    int minidx = get_min_idx(0, N-1, start, end, 1);
    if (minidx == -1) return 0;
    long long ret = (end-start+1LL)*arr[minidx];
    if (minidx > 0) ret = max(ret, solve(start, minidx-1));
    if (minidx < N-1) ret = max(ret, solve(minidx+1, end));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        cin >> N;
        if (!N) break;

        arr.resize(N);
        int h = (int)ceil(log2(N));
        int size = (1<<h+1);
        tree.resize(size);

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

        init(0, N-1, 1);
        cout << solve(0, N-1) << '\n';
    }

    return 0;
}

여담

넓이의 합이 int 범위를 벗어날 수 있으니 조심. 이거 스택으로 O(N)에 푸는 방법이 있긴 한데 생각하기 좀 어렵다.
백준 선생님이 야무지게 설명해놨으니 참고.