백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE

[문제 링크 : 1725 히스토그램]

[문제 링크 : 6549 히스토그램에서 가장 큰 직사각형]

[문제 링크 : FENCE]

세 문제가 모두 같은 문제이다. 이 정도로 같은 문제가 있는 것 보면 정말 유명한 문제인 것 같다. 이 문제를 풀 수 있는 방법은 여러개이다.

예전에 내가 풀었던 방식은 분할정복이었는데.

스택 문제 복습 겸 스택으로 풀도록 노력하였다.

스택을 통해 스위핑 알고리즘으로 푼다는데 이에 대한 설명은 구종만님의 책에도 있지만 개인적으로 너무 이해가 힘들었다.

스택을 이용해서 풀 때, 가장 왼쪽부터 차례대로 스택에 삽입하여 문제를 해결해간다.

스택에 막대를 삽입하는 조건은 '삽입하려고 하는 막대가, TOP에 있는 막대의 높이보다 클 때'이다.

만약 다음에 삽입하려는 막대가 현재 스택 TOP에 있는 막대보다 작으면, TOP에 있는 막대 높이로 만들 수 있는 직사각형의 오른쪽 끝이 된다.

그 경우 top을 pop하여 너비를 구한다. pop하기 전에 있던 top의 값을 tmp에 저장한다고 해보자. pop후의 스택의 top값은 tmp 왼쪽의 tmp보다 작은 막대이므로, 이 직사각형의 왼쪽 끝이 된다.

즉 tmp의 높이로 만들 수 있는 직사각형의 크기 = h[tmp] * (right - stack.top - 1)

위의 로직을 이해했으면 같을 경우에 굳이 스택에 인덱스를 삽입하지 않는 이유도 이해가 갈 것이다.

반복문을 다 돌았을 때 스택에 값이 남아있으면 이는 최대 직사각형에서 오른쪽 끝이, 전체의 오른쪽 끝인 직사각형들이다. 위에서 구한 공식대로 그 값들을 구해 최대값을 찾으면 된다. 

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
long long n, arr[100001];
long long histogram(){
    stack<long long> st;
    long long i,ret = 0;
    //스택에 왼쪽 끝 인덱스값을 미리 삽입해둔다. 
    st.push(-1);
    for(i=0; i<n;i++){
        //스택이 비어있지 않고,  
        while(!st.empty()&&arr[i]<arr[st.top()]){
            //right는 i 
            int tmp = st.top(); st.pop();
            if(!st.empty())
                //left는 st.top
                //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이 
                ret = max(ret, arr[tmp]*(i-st.top()-1));
        }
        //너비를 다 구하고 다음 판자를 스택에 삽입.
        st.push(i); 
    }
    //히스토그램을 끝까지 스택에 넣었는데도 안끝났다면
    //스택에 남아있는 판자들에서의 최대값을 구한다. 
    while(!st.empty()) {
        int tmp = st.top(); st.pop();
        if(!st.empty())
            ret = max(ret, arr[tmp]*(i-st.top()-1));
    }
    return ret;
}
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    printf("%lld\n",histogram());
    
}   

참고 : https://www.acmicpc.net/blog/view/12