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

문제

 

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

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

 

 

풀이

 

스택을 이용하여 해결할 수 있는 문제다. 스택에는 배열의 인덱스를 저장한다. 배열의 값이 증가하는 경우면 스택에 인덱스를 차례대로 저장한다. 높이가 증가하는 경우 이전 사각형은 다음 사각형 안에도 포함될 수 있다. 반대로 배열의 값이 감소하는 경우에는 직사각형의 넓이를 구해야한다. 이전 사각형이 다음 사각형 안에 포함될 수 없기 때문이다. 

 

높이 정보를 저장한 배열을 a라 한다. 스택의 top에는 이전 사각형의 인덱스 번호가 들어있다. 따라서 넓이를 구하려는 사각형의 높이 h = a[stack.top()]이 된다. 그 후 스택의 top을 pop해준다. 사각형의 가로는 현재 인덱스 i를 이용해서 구한다. i - stack.top() - 1을 해주면 넓이를 구하려는 사각형의 가로 길이가 나오게 된다. 구한 가로 세로 길이를 이용해서 가장 큰 넓이를 가지는 사각형을 찾으면 된다.

 

그리고 반복문이 다 돌고 난 이후 스택에 인덱스 값이 남아 있을 수 있다. 이 때는 가로 길이를 n으로 하고 위에 과정을 반복하면 위에서 구하지 못한 사각형들의 넓이를 구할 수 있다. 

 

 

코드

 

#include <iostream>
#include <stack>
 
using namespace std;
 
int n;
int a[100000];
stack<int> st;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    while (true)
    {
        cin >> n;
        if (n == 0) break;
        long long max = 0;
 
        for (int i=0; i<n; i++) cin >> a[i];
 
        for (int i=0; i<n; i++) 
        {
            while (!st.empty() && a[i] < a[st.top()])
            {
                long long h = a[st.top()];
                st.pop();
                long long l = i;
 
                if(!st.empty()) l = i-st.top()-1;
                if (max < l*h) max = l*h;
            }
            st.push(i);
        }
 
        while (!st.empty())
        {
            long long h = a[st.top()];
            long long l = n;
            st.pop();
            if (!st.empty()) l = n-st.top()-1;
            if (max < l*h) max = l*h;
        }
        cout << max << '\n';
    }
 
    return 0;
}