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

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

 히스토그램에서 가장 넓은 직사각형을 구하는 것은, Range query로 히스토그램의 특정 구간의 가장 짧은 직사각형의 높이를 찾아 구간의 너비를 곱하는 것과 같다.

 

 따라서 Segment Tree를 이용해 트리의 각 노드가 가장 짧은 직사각형의 높이를 저장하도록 구현하고, 구간으로 가능한 모든 경우에 대해 구간 질의하며 직사각형의 최대 넓이를 찾아 해결할 수 있는 문제이다.

=> Range query 결과가 해당 구간에서 가장 짧은 직사각형의 높이이므로, 쿼리 결과 x 구간 너비로 직사각형의 넓이를 구한 뒤 최대값을 갱신해 해결할 수 있다.

 

 그러나 build에는 O(n) 시간이 걸리므로 문제 없지만, range query에 O(log n) 시간이 걸리므로  구간으로 가능한 모든 경우에 대해 구간 질의하기엔 시간이 충분하지 않다.

 따라서 구간 질의할 구간 중 적절한 구간만을 선택해 수를 줄일 방법을 찾아야 한다.

 

[ 풀이 방법 ]

 구간 선정 방법을 찾지 못해 다른 사람의 풀이를 보고 풀 수 있었다.

 

 넓이의 최대값을 찾기 위해서는 현재 탐색한 구간보다 더 큰 결과를 얻을 수 있는 구간을 찾는 것이 필요하다.

이 때, 구간에서 가장 짧은 높이가 같다면 구간의 너비가 큰 구간이 항상 더 큰 결과를 얻을 것이다.

즉,  더 큰 넓이를 얻기 위해서는 구간의 너비가 더 크거나 구간의 가장 짧은 높이가 더 큰 값을 갖는 구간만 추가로 탐색하면 된다.

 

따라서 가장 큰 너비를 갖는 전체 구간부터 시작하여, 현재 구간보다 구간의 너비는 더 작으면서 구간의 가장 짧은 직사각형의 높이가 더 크도록 다음으로 탐색할 구간을 설정해야 한다.

 

 분할 정복을 이용해 위 기능을 주어진 시간 제한을 초과하지 않도록 구현할 수 있다.

=> Segment Tree에 저장된 구간에서 가장 짧은 직사각형의 높이를 이용해 직사각형의 넓이를 구하고, 해당 히스토그램 구간에서 가장 짧은 직사각형을 제외한 나머지 양쪽 구간을 탐색하며 최대값을 갱신하는 과정을 반복한다.

 처음에 히스토그램의 전 구간에서 시작해, 위 방법을 통해 구간의 크기가 0이 될 때까지 반복한다면 시간 초과없이 최대 넓이를 구할 수 있다.

 

 이 때, 히스토그램 구간에서 가장 짧은 직사각형의 위치를 빠르게 찾을 수 있도록 Segment Tree를 만들 때, 가장 짧은 직사각형의 높이가 아니라 가장 짧은 직사각형의 위치를 저장해야 한다.

세그먼트 트리(Segment Tree)

이전에 작성한 세그먼트 트리 구조체를 문제에 맞게 수정하여 build와 query 메서드를 구현하고 분할정복을 이용해 탐색할 구간을 찾는 기능을 구현해 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

typedef long long ll;

struct SegmentTree {
    int n;
    int e;
    vector<ll> tree;
    vector<ll> arr;
    
    void init(vector<ll>& origin) {
        arr.assign(origin.begin(), origin.end());
        n = int(arr.size());
        e = 1<<30;
        tree.resize(4*n);
        
        build(1, 0, n-1);
    }
    
    ll merge(ll leftValue, ll rightValue) {
        return arr[leftValue] < arr[rightValue] ? leftValue : rightValue;
    }
    
    ll build(ll node, ll nodeLeft, ll nodeRight) {
        if(nodeLeft == nodeRight) {
            return tree[node] = nodeLeft;
        }
        
        ll mid = nodeLeft - (nodeLeft - nodeRight)/2;
        ll leftValue = build(node*2, nodeLeft, mid);
        ll rightValue = build(node*2+1, mid+1, nodeRight);
        
        return tree[node] = merge(leftValue, rightValue);
    }
    
    ll query(ll left, ll right) {
        return queryRec(1, left, right, 0, n-1);
    }
    
    ll queryRec(ll node, ll left, ll right, ll nodeLeft, ll nodeRight) {
        
        if(left <= nodeLeft && nodeRight <= right) {
            return tree[node];
        }
        
        if(nodeRight < left || right < nodeLeft) {
            return e;
        }
        
        ll mid = nodeLeft - (nodeLeft - nodeRight)/2;
        
        ll leftValue = queryRec(node*2, left, right, nodeLeft, mid);
        ll rightValue = queryRec(node*2+1, left, right, mid+1, nodeRight);
        
        if(leftValue == e) return rightValue;
        else if(rightValue == e) return leftValue;
        else return merge(leftValue, rightValue);
    }
    
    void clear() {
        vector<ll>().swap(arr);
        vector<ll>().swap(tree);
    }
};

SegmentTree st;
ll res;

void solve(ll left, ll right) {
    
    if(left > right) return;
    
    ll minIdx = st.query(left, right);
    ll w = st.arr[minIdx] * (right-left+1);
    res = max(res, w);
    
    solve(left, minIdx-1);
    solve(minIdx+1, right);
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    while (cin >> n) {
        
        if(!n) break;
        
        vector<ll> arr(n);
        
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        res = 0;
        st.init(arr);
        
        solve(0, n-1);
        
        cout << res << '\n';
        
        st.clear();
        vector<ll>().swap(arr);
    }
    
    return 0;
}