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

분류: 스택 /

 

문제

문제 링크

문제 설명

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h₁, ..., h_n (0 ≤ h_i ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

풀이

#include <iostream>
#include <stack>
#define ll long long
using namespace std;

struct rect {int idx, h;};
ll max(ll a, ll b) {return a > b ? a : b;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        int n; cin >> n;
        if(n == 0) break;
        stack<rect> S;
        ll ans = 0;
        for(int i = 0; i < n; i++) {
            int h, idx = i; cin >> h;
            while(!S.empty() && S.top().h > h) {
                idx = S.top().idx;
                ans = max(ans, (ll)S.top().h * (i - idx));
                S.pop();
            }
            if(S.empty() || S.top().h < h) 
                S.push({idx, h});
        }
        while(!S.empty()) {
            ans = max(ans, (ll)S.top().h * (n - S.top().idx));
            S.pop();
        }
        cout << ans << '\n';
    }
}

 

마지막에 0을 넣어준 것으로 만들어 마지막 while문을 처리할 수 있다.

for(int i=0; i<=n; i++){
    int h, idx = i;
    if(i == n) h = 0;
    else cin >> h;
    
    while(!S.empty() && S.top().h > h) {
        idx = S.top().idx;
        ans = max(ans, (ll)S.top().h * (i - idx));
        S.pop();
    }
    if(S.empty() || S.top().h < h)
        S.push({idx, h});
}

 

 

[백준 - 1725] 히스토그램 문제와 같은 문제다 답을 `long long`으로 처리해줘야하는 부분 조심