[BOJ 14727] 퍼즐 자르기 (c++)

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

문제 개요

히스토그램 모양의 플라스틱 퍼즐 조각에서 가장 큰 직사각형을 잘라내려고 합니다. 히스토그램의 정보는 각 직사각형의 높이로 주어지며, 각 직사각형의 너비는 모두 1입니다. 주어진 히스토그램에서 잘라낼 수 있는 가장 큰 직사각형의 넓이를 구하는 문제입니다.

• (1 ≤ N ≤ 100,000)
• (1 ≤ Hi ≤ 1,000,000)

---

문제 풀이

이 문제는 세그먼트 트리와 분할 정복 기법을 활용하여 해결하였습니다.

핵심 아이디어는 다음과 같습니다.

1. 최소값 세그먼트 트리 구축: 구간 내에서 최소 높이를 가지는 직사각형의 정보(높이와 인덱스)를 빠르게 찾기 위해 세그먼트 트리를 구축합니다.
2. 분할 정복 전략: 특정 구간 [s, e]에서 가장 큰 직사각형을 찾기 위해 다음 세 가지 경우를 고려합니다.
   • 구간 전체를 포함하는 직사각형: 구간의 최소 높이 × 구간의 너비
   • 최소 높이 인덱스 기준 왼쪽 구간의 최대 직사각형
   • 최소 높이 인덱스 기준 오른쪽 구간의 최대 직사각형
3. 재귀적 탐색: 최소 높이를 기준으로 구간을 왼쪽과 오른쪽으로 분할하여 재귀적으로 탐색합니다. 최소 높이보다 큰 직사각형은 반드시 왼쪽이나 오른쪽 구간에만 존재하기 때문에, 중복 없이 모든 경우를 확인할 수 있습니다.
4. 최적화: 세그먼트 트리를 사용하여 구간 최소값 쿼리를 O(log N)에 처리함으로써 전체 시간 복잡도를 O(N log N)으로 유지합니다.

---

코드

#include 
#include 
using namespace std;

const int MAX = 1e9;

int n;
int arr[100001];
long long res;

class node {
public:
    int mn, x;
}seg[100001 * 4];

node init(int x, int s, int e) {
    if (s == e) return seg[x] = { arr[s], s };
    int mid = s + (e - s) / 2;
    node left = init(x * 2, s, mid);
    node right = init(x * 2 + 1, mid + 1, e);
    if (left.mn > right.mn) return seg[x] = right;
    else return seg[x] = left;
}

node query(int x, int s, int e, int l, int r) {
    if (r < s || e < l) return { MAX, -1 };
    if (l <= s && e <= r) return seg[x];
    int mid = s + (e - s) / 2;
    node left = query(x * 2, s, mid, l, r);
    node right = query(x * 2 + 1, mid + 1, e, l, r);
    if (left.mn > right.mn) return right;
    else return left;
}

void find_min(int s, int e) {
    node ret = query(1, 0, n - 1, s, e);
    long long tmp = (long long)ret.mn * (long long)(e - s + 1);
    res = max(res, tmp);
    if(ret.x > s)
        find_min(s, ret.x - 1);
    if(ret.x < e)
        find_min(ret.x + 1, e);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    init(1, 0, n - 1);
    find_min(0, n - 1);
    cout << res << '\n';
    return 0;
}