[백준/BOJ] 1725번: 히스토그램 ( 스택 stack 활용법 ) - C++ 문제풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/1725

 

풀이

이 문제는 주어진 히스토그램에 넣을 수 있는 가장 큰 직사각형의 넓이를 구하는 문제입니다.

 

이 문제를 푸는 아이디어는,

입력되는 막대의 높이가 줄어들면, 넣을 수 있는 직사각형의 높이가 줄어들므로,

줄어들기 전의 직사각형의 넓이가 가장 큰 값의 후보가 된다는 것입니다.

 

예를 들어, 간단한 경우를 생각해 보죠.

[4, 4, 4, 1]의 히스토그램이 입력되었을 때, 가장 큰 직사각형의 넓이를 구하는 과정을 생각해 보면

 

[4, 4, 4, 1] 히스토그램

 

4가 세 번 입력될 때까지, 직사각형의 높이는 4입니다.

그런데, 아직은 계산을 할 필요가 없습니다.

다음에 4보다 크거나 같은 높이의 막대가 입력되면, 최대 넓이가 더 늘어나기 때문입니다.

 

하지만, 다음에 1이 입력되면, 지금까지의 최대 높이의 직사각형이 더 늘어날 경우는 전혀 없습니다.

따라서, 높이 4의 3칸 막대의 넓이를 계산해 저장해 놓습니다.

만일, 이 값보다 더 큰 값이 입력되지 않으면, 이 값을 최대 값으로 출력하면 됩니다.

 

그리고, 높이 1의 4칸 직사각형도 만들 수 있습니다.

높이가 이전보다 낮으므로, 이전 막대 칸까지 포함할 수 있기 때문입니다.

이 직사각형의 넓이도 최대 값과 비교하면, 가능한 모든 직사각형을 계산한 것이 됩니다.

 

이를 소스 코드로 작성하면 다음과 같습니다.

typedef pair<int, int> MPAIR;	// 막대의 높이와 개수

// 마지막 저장된 막대와의 비교만 필요하므로 스택 구조가 편리합니다.
stack<MPAIR> st;	

int max_area = 0;	

for( int i = 0; i < N; i++){	// N은 모든 막대의 개수

    cin >> A;	// 히스토리 막대 높이 입력

    cnt = 0;	// 막대의 개수
    
    // 이전 막대보다 높이가 낮으면
    while( !st.empty() && st.top().first >= A){
        
        // 이전 직사각형의 넓이를 계산해서 저장
        const MPAIR& p = st.top();
        int area = p.first * (p.second + cnt);
        if ( max_area < area) max_area = area;
        
        cnt += p.second;	// 막대의 개수를 누적시킨다.

        st.pop();	// 계산을 마쳤으므로 스택에서 제거
    }

    MPAIR p( A, cnt+1);	// 낮은 높이의 막대로 교체
    st.push(p);
}

위의 코드는 낮은 높이의 막대가 입력되면, 이전의 직사각형 넓이를 계산 후 저장합니다.

그럼 이전의 막대는 이제 낮은 높이의 막대 역할을 할 것이기 때문에,

이를 제거하고, 대신에 낮은 높이의 막대의 개수를 늘리는 코드입니다.

만약, 같은 높이의 막대가 입력되더라도, 이전의 막대는 제거하는 대신, 막대의 개수를 늘리는 방식을 썼습니다.

 

이제, 마지막으로 스택에 높이-오름차순으로 남아있는 막대들의 넓이를 계산하면, 모든 직사각형을 계산할 수 있습니다.

cnt = 0;	// 막대의 개수

while( !st.empty()){
    
    const MPAIR& p = st.top();
    cnt += p.second;

    int area = p.first * cnt;
    if ( max_area < area) max_area = area;
    
    st.pop();  
}

이제, 저장해 둔 최대 넓이를 출력하면 문제 해결입니다.

 

 

소스 코드

#include <iostream>
#include <stack>
using namespace std;

typedef pair<int, int> MPAIR;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, A, cnt;
    cin >> N;

    stack<MPAIR> st;

    int max_area = 0;

    for( int i = 0; i < N; i++){

        cin >> A;

        cnt = 0;
        while( !st.empty() && st.top().first >= A){
            
            const MPAIR& p = st.top();
            int area = p.first * (p.second + cnt);
            if ( max_area < area) max_area = area;
            
            cnt += p.second;

            st.pop();
        }

        MPAIR p( A, cnt+1);
        st.push(p);
    }

    cnt = 0;
    while( !st.empty()){
        
        const MPAIR& p = st.top();
        cnt += p.second;

        int area = p.first * cnt;
        if ( max_area < area) max_area = area;
        
        st.pop();  
    }

    cout << max_area;

    return 0;
}