[백준6549] 히스토그램에서 가장 큰 직사각형 - 분할정복

분할정복 (Devide and Conquer)

분할-정복 방법은 말 그대로 하나의 문제를 둘로 분할하여 생각하여 해결하는 방법론이다. 병합정렬(merge sort)이 대표적이다. 분할-정복 문제는 문제를 둘로 분할하는 파트와, 분할 하여 구한 값을 통해 주워진 원래의 문제의 답을 도출하는 과정으로 나뉜다. 이때 어려운 문제는 보통 후자에서 높은 난이도를 자랑한다.

오늘 알아볼 **“히스토그램에서 가장 큰 직사각형”**문제도 분할하여 얻은 결과를 통해 어떻게 답을 도출할지에 대해 깊이 고민해야 하는 문제이다.

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

히스토그램 내애 직사각형을 그렸을 때, 가장 큰 직사각형의 넓이를 구하는 문제이다. 직사각형의 밑변은 수평축에 포함된다.

 

일단 위 문제를 분할해보자. 일단 히스토그램을 둘로 나눠 각각의 히스토그램에서 가장 큰 직사각형을 구하면 된다.

ll getBigRectangle(int l, int r) {
    
    if (l == r) return histogram[l];
    
    int m = (l + r) / 2;
    
    ll left = getBigRectangle(l, m);
    ll right = getBigRectangle(m+1, r);
    
    ll ret = (left > right) ? left : right;

		//// 답을 어떻게 구할까?
    
    return ret;
}

오른쪽 히스토그램, 왼쪽 히스토그램 이렇게 둘로 나눠 각각의 히스토그램에서의 가장 큰 직사각형을 구하였다. 그렇다면 답을 어떻게 구할까?

 

Idea. 분할을 통해 도출된 두 직사각형 중 큰 직사각형을 고른다

단순하게 위와 같이 생각할 수 있다. 하지만 이것만으로는 답을 구할 수 없다. 왜냐하면 두 범위를 모두 포함하는 직사각형이 최대일 수 있기 때문이다.

 

이 문제의 핵심 포인트는 “두 범위를 모두 포함하는 직사각형중 최대를 어떻게 구할 것인가” 이다.

범위를 위 그림과 같이 둘로 나눴다고 생각해보자. 그러면 일단 경계선과 인접한 양쪽의 막대를 반드시 포함하게 된다. 그 후 직사각형을 넓혀가며 탐색을 하게 되는데 이때 완전 탐색을 하면 O(n^2)의 시간복잡도가 필요하게 된다. n<100000 범위에서는 시간초과(1초 기준)가 발생하게 된다.

 

그렇다면 완전탐색보다 더 빠른 탐색 방법이 필요하다. 이때 사용하는 것이 그리디 알고리즘이다. 히스토그램 탐색전략은 아래와 같다.

 

“현재까지 탐색한 직사각형과 인접한 양쪽 두 막대 중 무조건 더 긴 막대쪽으로 탐색한다”

 

그리디 알고리즘을 사용한다면 모든 막대를 한번씩 탐색하므로 O(n)의 시간 복잡도가 필요하다.

ll conquer(int l, int m, int r) {
    int left = m;
    int right = m + 1;
    
    ll width = 2;
    ll height = (histogram[left] > histogram[right]) 
                    ? histogram[right] : histogram[left];
    
    ll ret = width * height;
    left--;
    right++;
    width++;
    
    while (l <= left && right <= r) {
        
        if (histogram[left] > histogram[right]) {
            height = (height > histogram[left]) ? histogram[left] : height;
            left--;
        } else {
            height = (height > histogram[right]) ? histogram[right] : height;
            right++;
        }
        
        if (ret < width * height) ret = width * height;
        width++;
    }
    
    while (l <= left) {
        height = (histogram[left] < height) ? histogram[left] : height;
        if (ret < width * height) ret = width * height;
        left--;
        width++;
    } 
    
    while (right <= r) {
        height = (histogram[right] < height) ? histogram[right] : height;
        if (ret < width * height) ret = width * height;
        right++;
        width++;
    }
    
    return ret;
}

위 코드는 경계(m)을 기준으로 양쪽 범위를 모두 포함하는 가장 큰 직사각형을 구하는 코드이다.

 

while문 안쪽 if 문을 보면 왼쪽 막대(histogram[left])와 오른쪽 막대(histogram[right])중 더 긴 막대를 선택하여 현재 높이와 비교하여 직사각형의 넓이를 갱신한다.

 

Solution

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

vector<int> histogram(100000);

ll conquer(int l, int m, int r) {
    int left = m;
    int right = m + 1;
    
    ll width = 2;
    ll height = (histogram[left] > histogram[right]) 
                    ? histogram[right] : histogram[left];
    
    ll ret = width * height;
    left--;
    right++;
    width++;
    
    while (l <= left && right <= r) {
        
        if (histogram[left] > histogram[right]) {
            height = (height > histogram[left]) ? histogram[left] : height;
            left--;
        } else {
            height = (height > histogram[right]) ? histogram[right] : height;
            right++;
        }
        
        if (ret < width * height) ret = width * height;
        width++;
    }
    
    while (l <= left) {
        height = (histogram[left] < height) ? histogram[left] : height;
        if (ret < width * height) ret = width * height;
        left--;
        width++;
    } 
    
    while (right <= r) {
        height = (histogram[right] < height) ? histogram[right] : height;
        if (ret < width * height) ret = width * height;
        right++;
        width++;
    }
    
    return ret;
} 


ll getBigRectangle(int l, int r) {
    
    if (l == r) return histogram[l];
    
    int m = (l + r) / 2;
    
    ll left = getBigRectangle(l, m);
    ll right = getBigRectangle(m+1, r);
    
    ll ret = (left > right) ? left : right;
    
    ll mid = conquer(l, m, r);
    
    ret = (ret > mid) ? ret : mid;
    
    return ret;
}

int main() {
    int n;
    cin >> n;
    
    while (n != 0) {
        for (int i=0; i<n; ++i) {
            cin >> histogram[i];
        }
        cout << getBigRectangle(0, n-1) << "\n";
        cin >> n;
    }
}