[백준 2571] 색종이 -3

문제

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

알고리즘

스택

풀이

최대 직사각형의 크기를 구하는 문제입니다.

히스토그램에서 가장 큰 직사각형 문제와 동일하게 풀면 됩니다. 각 사각형의 높이가 직접 주어지는 것이 아니므로 높이를 추적할 수 있는 $height[i]$ 배열을 사용했습니다. 스택 안에 직사각형 높이가 오름차순이 되도록 유지하며 만약 현재 높이가 스택의 top보다 작다면 스택의 top을 최대 높이로 하는 직사각형의 넓이를 결정할 수 있습니다.

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef pair<int, int> pii;

int board[105][105], height[105], ans;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    rep(i, N) {
        int u, v;
        cin >> u >> v;
        for (int j = u; j < u + 10; ++j) {
            for (int k = v; k < v + 10; ++k) {
                board[j][k] = 1;
            }
        }
    }

    for (int i = 0; i < 100; ++i) {
        stack<pii> stk;
        for (int j = 0; j < 101; ++j) {
            if (board[i][j] == 1) height[j] += 1;
            else
                height[j] = 0;

            while (stk.size() && stk.top().first >= height[j]) {
                auto [h, idx] = stk.top();
                stk.pop();

                int L = stk.empty() ? -1 : stk.top().second;
                ans = max(ans, (j - L-1) * h);
            }
            stk.emplace(height[j], j);
        }
    }
    cout << ans;
    return 0;
}