[C++] 6549 - 히스토그램에서 가장 큰 직사각형 (플래티넘5)

1. 문제 설명

 

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

1725번: 히스토그램

테스트 케이스가 한 개 뿐인 동일한 티어의 문제가 또 있다.

경험치 2배 이벤트 댕꿀~

 

algospot.com :: FENCE

참고로 이 문제랑 동일하다.

---

2. 아이디어

 

알고리즘 문제를 풀면서 생각해보아야 할 것들

 

이 문제는 이전에 진득하게 다뤘으므로 위의 포스팅을 참조하면 된다.

값이 크기 때문에 시간 복잡도를 최소로 줄여야 하는데 스택과 스위핑 기법을 이용한다면

선형 시간 알고리즘으로 문제를 해결할 수 있다.

 

그런데 오랜만에 푸니까 또 헷갈려서 생각보다 제법 시간이 걸렸다.

---

3. 코드

 

#include <iostream>
#include <stack>

#define endl "\n"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll calc_area(int n) {
    int idx = 0, height;
    ll w, h;
    ll max_area = 0;
    pii tmp;
    stack<pii> st; st.push(make_pair(0, -1)); // {y, x}

    while (idx <= n) {
        if (idx == n) height = 0; 
        else cin >> height;
         
        while (!st.empty() && st.top().first >= height) {
            tmp = st.top(); st.pop();

            h = tmp.first;
            w = (st.empty()) ? idx : idx - st.top().second - 1;

            max_area = max(max_area, (ll)w*h);
        }
        st.push(make_pair(height, idx));

        idx++;    
    }

    return max_area;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; 

    while (true) {
        cin >> n;
        if (n == 0) break;
        cout << calc_area(n) << endl;
    }

    return 0;
}