백준 6549번 [히스토그램에서 가장 큰 직사각형](C++)-yes6686- 티스토리

백준 문제 풀이: 6549 [히스토그램에서 가장 큰 직사각형]

---

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

문제 설명:

히스토그램이 주어졌을 때, 가장 큰 직사각형의 넓이를 계산하는 문제입니다. 히스토그램은 너비가 1인 n개의 직사각형으로 구성되며, 직사각형의 높이는 입력으로 주어집니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#define INF 2000000000
using namespace std;

long long int arr[100001];
long long int seg[400001];

int go(int n, int s, int e) {
    if (s == e) {
        seg[n] = s;
        return seg[n];
    }
    else {
        int mid = (s + e) / 2;
        int left = go(2 * n, s, mid);
        int right = go(2 * n + 1, mid + 1, e);
        if (arr[left] > arr[right]) {
            seg[n] = right;
        }
        else {
            seg[n] = left;
        }
        return seg[n];
    }
}

int fi(int n, int s, int e, int l, int r) {
    if (e < l || r < s) return INF;
    if (l <= s && r >= e) {
        return seg[n];
    }
    int mid = (s + e) / 2;
    int left = fi(n * 2, s, mid, l, r);
    int right = fi(n * 2 + 1, mid + 1, e, l, r);
    if (left == INF) return right;
    if (right == INF) return left;
    return arr[left] < arr[right] ? left : right;
}

long long int maxArea = -1;
int n;

void solve(int s, int e) {
    if (s > e) return;

    int index = fi(1, 0, n - 1, s, e);
    if (maxArea < arr[index] * (e - s + 1)) {
        maxArea = arr[index] * (e - s + 1);
    }
    solve(s, index - 1);
    solve(index + 1, e);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (1) {
        maxArea = -1;
        cin >> n;
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        go(1, 0, n - 1);
        solve(0, n - 1);
        cout << maxArea << '\n';
    }
}

---

코드 설명

• 핵심 알고리즘: 분할 정복과 세그먼트 트리를 활용하여 가장 작은 높이의 직사각형을 기준으로 문제를 재귀적으로 해결합니다.
• 구현 세부사항:
  • go 함수: 세그먼트 트리를 초기화하여 각 구간에서 가장 작은 높이의 인덱스를 저장합니다.
  • fi 함수: 주어진 구간에서 가장 작은 높이의 인덱스를 반환합니다.
  • solve 함수: 가장 작은 높이를 기준으로 왼쪽과 오른쪽 구간을 재귀적으로 분할하여 최대 넓이를 계산합니다.
• 시간 복잡도: O(n log n)
  • 세그먼트 트리 초기화: O(n)
  • 구간 최소 값 질의: O(log n)
  • 전체 문제 해결: O(n log n) (분할 정복)

---

결과

주어진 히스토그램에서 가장 큰 직사각형의 넓이를 효율적으로 계산했습니다. 세그먼트 트리와 분할 정복을 조합한 알고리즘을 통해 입력 크기가 큰 경우에도 빠르게 처리할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!