[백준] [C++] 6549번 히스토그램에서 가장 큰 직사각형(sweeping, 분할 정복, stack)

1. 문제

 

6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net)

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

 

2. 분할정복

직사각형이 있는 경우의 수는 한 부분문제에서 총 3가지의 경우 로 나눌 수 있다.

 

1. 왼쪽~ 중간 쪽에 최대인 직사각형이 있는 경우

2. 중간~오른쪽  쪽에 최대인 직사각형이 있는 경우

3. 중간을 포함하여 위의 두 영역에 걸쳐 있는 경우

 

직관적으로 한 문제당 왼쪽, 오른쪽 두개의 부분문제로 나뉘어지고, 

 

중간을 포함하는경우는 주어진 문제에서 풀어야할 문제라는 것을 알 수 있다.

 

이들을 다음과 같이 나타낼 수 있다.

 

maxSquare(left, right) = mid 를 포함하고 left~right 구간안에서의 최대 사각형 solve(left, right) = max( maxSquare(left, right)  , solve(left, mid) , solve(mid, right))                          (left +1 == right 일 경우 높이 * 1를 반환)

 

위 식들을 코드로 다음과 같이 작성할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
 
using namespace std;
 
ll n;
vector<ll> h;
 
ll sol1(ll left, ll right) {
    ll mid = (left + right)/2;
    ll midArea = h[mid], height = h[mid];
    ll l = mid - 1, r = mid + 1;
 
    if(left +1 >= right) {
        return midArea; 
    }
    while(l > left || r < right) {
        if(l <= left || (r < right && h[l] <= h[r])) {
            height = min(h[r], height);
            r++;
        }
        else {
            height = min(height, h[l]);
            l--;
        }
        ll width = r -1 - l; 
        midArea = max(midArea, width * height);
    }
    return max(midArea, max(sol1(left, mid), sol1(mid, right)));
}
 
int main() {
    while(true) {
       cin>>n;
       if(n == 0) {
           break;
       }
       h = vector<ll>(n+2);
       h[0] = h[n+1] = 0;
       for(int i = 1; i <= n; i++) {
           cin>>h[i];
       }
       cout<<sol1(0, n+1)<<"\n";
    }
}

 

3. Sweeping, stack

stack을 사용하면  O(N)만에 해결 할 수 있다.

 

직사각형의 넓이를 결정짓는것은 left와 right 그리고 높이 이다.

 

각각의 직사각형들의 left, right는 다음과 같이 결정된다.

3.1 left

    1) 첫번째 직사각형에서는 left는 항상 0이 된다 (첫번째의 인덱스가 1일때)

    2) 그 이외는 왼쪽에서 가장 가까운 자기보다 높이가 작은 직사각형이 left가 된다.

3.2 right

    1) 마지막 직사각형의 right는 항상 n+1 이 다 (첫번째의 인덱스가 1일때, 마지막은 n)

    2) 그 이외는 오른쪽에서 가장 가까운 자기보다 높이가 작은 직사각형이 right가 된다.

 

왼쪽에서부터 직사각형을 고려할때의 높이는 다음과 같다.

3.3 height

    1) 오른쪽의 높이가 더 낮을 경우, 더이상 현재의 높이를 유지하면서 넓이를 더 크게 만드는 것은 불가능하다.

    2) 고려하고 있는게  높이가 더 높은 경우, 기존의 높이를 유지하면서 더 크게 만드는 것이 가능하다.

 

 

위의 3가지 변수들을 통해, 결국 순차적으로 직사각형을 고려할때 높이가 낮아질 경우  

 

현재 직사각형이 right가 되어 이전의 더 높은 직사각형들이 최대가 되었음을 의미하며,

 

이제 고려대상에서 제외 되었음을 의미하는것이라는것을 알 수 있다.

 

 

따라서 이제 고려대상에는 현재 고려하고있는 직사각형보다 높이가 낮은것들 밖에 없게되므로,

 

고려대상의 최상단(가장 최근, 현재 직사각형보다 높이가 낮은)이 left가 됨을 알 수 있다.

 

 

이러한 방식을 자료구조 stack을 이용하여 표현할 수 있다.

 

스택에는 결국 높이가 높아지는 순으로 정렬이되어지며, 더 작은게 들어오게되면 right가 결정되어지고

 

스택에서 그보다 큰 직사각형들이 pop되어 고려대상에서 자동적으로 제외되며, 다시 최상단에는 pop된 것보다 낮은 직사각형이 있으므로, left 또한 결정되게 된다.

 

따라서 이때 까지 만들어진 직사각형들의 최대 면적과 현재 pop된 직사각형의 높이와 left right로 결정된 직사각형의 넓이와 비교하여 업데이트하면 

 

결국 전체 구간에서 면적이 최대인 직사각형을 만들 수 있게된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
 
#define ll long long
 
using namespace std;
 
ll n;
vector<ll> h;
 
ll sol1() {
    stack<ll> s; 
    ll ret = 0;
    for(ll i = 1; i <= n+1; i++) {
        while(!s.empty() && h[s.top()] >= h[i]) {
            int tmp = s.top(); s.pop();
            int width = i - ((s.empty())? 0 : s.top()) - 1;
            ret = max(ret, h[tmp]*width );
        }
        s.push(i);
    }
    return ret;
}
 
int main() {
    while(true) {
       cin>>n;
       if(n == 0) {
           break;
       }
       h = vector<ll>(n+2);
       h[0] = h[n+1] = 0;
       for(ll i = 1; i <= n; i++) {
           cin>>h[i];
       }
       cout<<sol1()<<"\n";
    }
}