---
id: "imported/blog/history/boj/boj-6549"
title: "BOJ 6549 (직사각형 최대 넓이 구하기)"
description: "예전에 스택으로 풀 수 있다는 이야기만 듣고 덮어놨었던 문제. 다이아몬드 가공 문제에서 최대 면적을 빠르게 구해야할 필요가 있어서 다시 꺼내 풀어보았다."
kind: "record"
published: "2023-05-10T00:00:00.000Z"
tags: ["PS","BOJ","stack"]
url: "https://www.readiz.com/blog/history/boj/boj-6549/"
markdownUrl: "https://www.readiz.com/blog/history/boj/boj-6549/index.md"
---

# BOJ 6549 (직사각형 최대 넓이 구하기)

- 문제 제목: 히스토그램에서 가장 큰 직사각형
- 문제 링크: <https://www.acmicpc.net/problem/6549>
- BOJ 해설: <https://www.acmicpc.net/blog/view/12>

예전에 스택으로 풀 수 있다는 이야기만 듣고 덮어놨었던 문제. 다이아몬드 가공 문제에서 최대 면적을 빠르게 구해야할 필요가 있어서 다시 꺼내 풀어보았다.

(사담이지만, 백준은 다양한 문제를 풀 수 있어서 좋은듯.. 이런 서비스가 한국에 있어서 분명 한국의 SW 경쟁력을 높힌다고 생각.)

SegTree나 분할정복으로 `O(n*log n)`이 걸리는 시간복잡도를 `O(n)` 으로 줄일 수 있는 획기적인 아이디어.

스택에는 항상 증가하는 순서로 height 들이 들어가 있으므로, pop 한 이후 `idx.top()`을 하게되면, 최대 width가 나온다. 이 부분이 핵심 아이디어.

전체 코드는 아래와 같다.

```cpp
void solve() {
    for (rint i = 1; i <= N; ++i) {
        scanf("%d", &A[i]);
    }
    A[0] = A[N+1] = 0;
    stack<int> idx;
    idx.push(0);

    ll maxArea = 0;
    for(rint i = 1; i <= N + 1; ++i) { // N + 1, 마지막 fake 원소로 끝내기 위함
        _D("checking A[%d] = %d\n", i, A[i]);
        while(idx.size() && A[idx.top()] > A[i]) {
            int c = idx.top(); idx.pop(); // 더 작으면 pop한다.
            ll w = i - idx.top() - 1; // c - i가 아님에 유의! **자기보다 더 작은 애가 있는 곳까지..
            ll h = A[c];
            ll area = w * h;
            _D("area: %lld\n", area);
            if (area > maxArea) maxArea = area;
        }
        idx.push(i); // 신규 원소 push
    }

    printf("%lld\n", maxArea);
}
```