[P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복

리뷰

 

세그먼트 트리를 응용하여 히스토그램 상에서 가장 큰 면적을 구하는 문제

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

 

전역 변수

lst : 히스토그램의 높이 정보를 저장할 정수형 배열, 최대 히스토그램 크기 10만으로 초기화 해준다.

tree : 세그먼트 트리 정보를 저장할 정수형 배열, lst의 4배 40만으로 크기를 초기화 해준다.

n : 히스토그램의 최대 갯수를 저장할 정수형 변수

 

 

함수

1. init

void init()

 

각 테스트 케이스 마다 lst와 tree를 0으로 초기화 해주는 함수

 

2. input

void input()

 

데이터를 입력 받고 히스토그램 높이 정보를 lst배열에 초기화 해주는 함수

 

3. build

void build(ll node, ll start, ll end)

 

1. 세그먼트 트리의 노드를 초기화 해주는 함수
2. 각 노드는 히스토그램 구간에서 최소값의 인덱스를 저장해 준다.

 

4. getIndex

ll getIndex(ll node, ll start, ll end, ll L, ll R)

 

1. 주어진 구간에서 가장 최소값을 갖는 히스토그램의 인덱스를 리턴해 주는 함수
2. 최소값이 아닌 최소값을 갖고 있는 히스토그램의 인덱스를 출력해 준다.

 

5. query

ll query(ll start, ll end)

 

1. 전체 구간에서의 넓이의 최대값을 찾고 리턴해 주는 함수
2. getIndex를 통해 최소값의 인덱스 min_index를 찾고, 주어진 구간과 해당 높이의 곱을 계산한다.
3. min_index를 기준으로 왼쪽, 오른쪽을 분할하여 재귀를 진행해 준다.
4. 현재 구간의 넓이 all, 왼쪽 구간의 넓이 left, 오른쪽 구간의 넓이 right중 가장 큰 수를 리턴해 준다.

 

문제풀이

1. 무한 루프를 실행하고 n값을 입력 받는다, 만약 n값이 0일 경우 루프를 종료한다.
2. init함수를 통해 현재 히스토그램과 세그먼트 트리 정보를 모두 초기화 해준다.
3. input함수를 통해 n개의 히스토그램 정보를 입력 받고 lst배열에 저장해 준다.
4. build함수를 통해 lst배열에 저장된 히스토그램 정보로 tree배열에 세그먼트 트리 정보를 저장한다.
5. query함수를 통해 전체 범위에서 히스토그램이 가질 수 있는 최대 넓이를 탐색해 준다.
6. 탐색이 종료된 후 리턴받은 최종 값을 출력해 준 뒤 줄바꿈을 수행해 준다.
7. n이 0이 나올때 까지 위 작업을 반복하여 수행해 준다.

 

참고 사항

1. 히스토그램의 최대 크기를 찾을 구간이 정해져 있지 않으므로 모든 부분에 대해 재귀를 통해 탐색을 진행해 주어야 한다.
2. 최소값을 갖는 히스토그램의 인덱스가 아닌 최소값을 저장, 출력해 준다면 어느 부분인지를 알 수 없기 때문에 세그먼트 트리는 최소값을 갖는 인덱스를 저장하고 있어야 한다.
3. 정수형 타입은 long long이어야 한다.

 

정답 코드

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;
ll lst[100000];
ll tree[400000];
ll n;

void init() {
    memset(lst, 0, sizeof(lst));
    memset(tree, 0, sizeof(tree));
}

void input() {
    for (int i = 0; i < n; i++) cin >> lst[i];
}

void build(ll node, ll start, ll end) {
    if (start == end) tree[node] = start;
    else {
        ll mid = (start + end) / 2;
        build(node * 2, start, mid);
        build(node * 2 + 1, mid + 1, end);
        tree[node] = (lst[tree[node * 2]] <= lst[tree[node * 2 + 1]]) ? tree[node * 2] : tree[node * 2 + 1];
    }
}

ll getIndex(ll node, ll start, ll end, ll L, ll R) {
    if (R < start || end < L) return -1;
    if (L <= start && end <= R) return tree[node];
    ll mid = (start + end) / 2;
    ll left = getIndex(node * 2, start, mid, L, R);
    ll right = getIndex(node * 2 + 1, mid + 1, end, L, R);

    if (left == -1) return right;
    if (right == -1) return left;
    return (lst[left] <= lst[right]) ? left : right;
}

ll query(ll start, ll end) {
    if (start > end) return 0;
    ll min_index = getIndex(1, 0, n - 1, start, end);
    ll all = lst[min_index] * (end - start + 1);
    ll left = query(start, min_index - 1);
    ll right = query(min_index + 1, end);

    return max({ all, left, right });
}

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

    while (1) {
        cin >> n;
        if (!n) break;
        init();
        input();
        build(1, 0, n - 1);
        cout << query(0, n - 1) << "\n";
    }
}