백준[6549] 히스토그램에서 가장 큰 정사각형

문제 설명

문제 링크

http://icpc.me/6549

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

풀이

스택과 분할 정복을 이용하여 풀 수 있다. 

스택을 이용한 풀이는 O(N)에 풀 수 있지만 아이디어를 떠올리기 힘들고, 분할 정복은 O(NlogN)에 풀 수 있지만 세그먼트 트리를 알아야 한다.

분할 정복

구간 [l, r]에서 가장 큰 직사각형의 넓이는 (가장 작은 기둥 높이) * (r - l + 1) 그렇기 때문에 가장 작은 기둥 왼쪽, 가장 작은 기둥 오른쪽으로 분할해가며 확인하면 된다. 이때 가장 작은 기둥의 인덱스를 세그먼트 트리로 관리를 해야 O(NlogN)에 해결이 가능하다.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;

void init(vector <ll> &arr, vector <ll> &tree, ll node, ll start, ll end) {
    if (start == end) tree[node] = start;
    else {
        ll mid = (start + end) / 2;
        init(arr, tree, node * 2, start, mid);
        init(arr, tree, node * 2 + 1, mid + 1, end);
        if (arr[tree[node * 2]] < arr[tree[node * 2 + 1]]) tree[node] = tree[node * 2];
        else tree[node] = tree[node * 2 + 1];
    }
}

ll query(vector <ll> &arr, vector <ll> &tree, ll node, ll start, ll end, ll i, ll j ) {
    if (end < i || start > j) return -1;
    else if (i <= start && end <= j) return tree[node];
    ll mid = (start + end) / 2;
    ll left = query(arr, tree, node * 2, start, mid, i, j);
    ll right = query(arr, tree, node * 2 + 1, mid + 1, end, i, j);
    if (left == -1) return right;
    else if (right == -1) return left;
    else if (arr[left] < arr[right]) return left;
    else return right;
}


ll solve(vector <ll> &arr, vector <ll> &tree, ll start, ll end) {
    ll N = arr.size() - 1;
    ll idx = query(arr, tree, 1, 1, N, start, end);
    ll ans = (end - start + 1) * arr[idx];
    if (start < idx) {
        ll tmp = solve(arr, tree, start, idx - 1);
        ans = max(ans, tmp);
    }
    if (idx < end) {
        ll tmp =  solve(arr, tree, idx + 1, end);
        ans = max(ans, tmp);
    }
    return ans;
}

int main() {
    while (true) {
        ll N; scanf("%lld", &N);
        if (N == 0) return 0;
        vector <ll> arr(N + 1);
        for (int i = 1; i <= N; i++) {
            ll tmp; scanf("%lld", &arr[i]);
        }
        ll height = (int)ceil(log2(N));
        ll tree_size = (1 << (height + 1));
        vector <ll> tree(tree_size);
        init(arr, tree, 1, 1, N);
        printf("%lld\n", solve(arr, tree, 1, N));
    }
    return 0;
}

스택

스택에 들어있는 값이 단조적으로 유지되게 하며 스택에 값과 그 인덱스를 잘 관리하면 된다.

스택의 top보다 큰 값이 들어온다면, 그냥 push 하고, 스택의 top보다 작은 값이 들어온다면, 들어올 값이 top보다 커질 때까지 pop을 하면 된다. pop을 할 때는 top의 앞에 있던 직사각형은 자신보다 큰 직사각형임이 보장되기 때문에 (i - top.idx) * top.heigt를 한다. 그리고 push를 할 때에는 pop을 했던 직사각형들을 이용하여 push 할 값이 큰 사각형을 만들 수 있기 때문에 pop 한 인덱스 중 가장 작은 인덱스를 push 한다.

#include <cstdio>
#include <stack>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

const int N = 1e5 + 5;
int n;
int h[N];

ll solve() {
    for (int i = 0; i < n; i++) scanf("%d", h + i);
    stack<pii> s;
    ll ret = 0;
    for (int i = 0; i < n; i++) {
        if (s.empty() || s.top().first <= h[i]) {
            s.push({h[i], i});
        } else {
            int l = i;
            while (!s.empty() && h[i] < s.top().first) {
                auto [k, idx] = s.top();
                ret = max(ret, ll(i - idx) * k);
                l = idx;
                s.pop();
            }
            s.push({h[i], l});
        }
    }
    while (!s.empty()) {
        auto [k, idx] = s.top();
        ret = max(ret, ll(n - idx) * k);
        s.pop();
    }
    return ret;
}

int main() {
    while (1) {
        scanf("%d", &n);
        if (n == 0) break;
        printf("%lld\n", solve());        
    }
}