백준 6549번 히스토그램에서 가장 큰 직사각형

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

지금까지 푼 세그먼트 트리 문제들은 간단한 구현 문제였지만 이번 문제는 응용을 해야하는 문제였습니다.

오랜 시간 고민 끝에도 접근 방법을 모르겠어서 Crocus님 포스팅(http://www.crocus.co.kr/707)을 참고했습니다.

접근 방법은 아래와 같습니다.

1. 세그먼트 트리를 초기화할 때 해당 구간 내 가장 낮은 막대의 인덱스를 저장합니다.

2. query 함수를 통해 구간 내 제일 낮은 막대의 높이를 구합니다.

3. getMaxArea 함수를 통해 해당 구간 내 최대 넓이를 구합니다.

i) query를 통해 구간 내 최소 높이를 갖는 막대의 인덱스를 구합니다.

ii) 해당 인덱스의 왼쪽에 막대가 존재할 경우 왼쪽 구간을 살핍니다

iii) 해당 인덱스의 오른쪽에 막대가 존재할 경우 오른쪽 구간을 살핍니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

 

//핵심은 최소 높이를 갖는 막대의 인덱스를 저장하는 것이다!

void init(vector<long long> &array, vector<long long> &tree, int node, int start, int end)

{

        //단말 노드

        if (start == end)

                 tree[node] = start;

        else

        {

                 int mid = (start + end) / 2;

                 init(array, tree, node * 2, start, mid);

                 init(array, tree, node * 2 + 1, mid + 1, end);

                 //각 구간에서 가장 높이가 낮은 것을 노드에 넣어준다

                 if (array[tree[node * 2]] < array[tree[node * 2 + 1]])

                         tree[node] = tree[node * 2];

                 else

                         tree[node] = tree[node * 2 + 1];

        }

}

 

//구간에서 가장 최소인 높이의 막대 인덱스 구하기

int query(vector<long long> &array, vector<long long> &tree, int node, int start, int end, int i, int j)

{

        if (end<i || start>j)

                 return -1;

        else if (i <= start && end <= j)

                 return tree[node];

 

        int mid = (start + end) / 2;

        int leftQuery = query(array, tree, node * 2, start, mid, i, j);

        int rightQuery = query(array, tree, node * 2 + 1, mid + 1, end, i, j);

 

        if (leftQuery == -1)

                 return rightQuery;

        else if (rightQuery == -1)

                 return leftQuery;

        else if (array[leftQuery] < array[rightQuery])

                 return leftQuery;

        else

                 return rightQuery;

}

 

long long getMaxArea(vector<long long> &array, vector<long long> &tree, int start, int end)

{

        int N = array.size() - 1;

        int idx = query(array, tree, 1, 1, N, start, end);

       

        long long area = (end - start + 1) * array[idx];

 

        //왼쪽 막대가 존재하는가

        if (start < idx)

        {

                 long long temp = getMaxArea(array, tree, start, idx - 1);

                 area = max(area, temp);

        }

        //오른쪽 막대가 존재하는가

        if (idx < end)

        {

                 long long temp = getMaxArea(array, tree, idx + 1, end);

                 area = max(area, temp);

        }

        return area;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

 

        while (1)

        {

                 int N;

                 cin >> N;

                 if (N == 0)

                         break;

 

                 vector<long long> arr(N + 1);

 

                 for (int i = 1; i <= N; i++)

                         cin >> arr[i];

 

                 //세그먼트 트리 크기

                 int height = (int)ceil(log2(N));

                 int tree_size = (1 << (height + 1));

 

                 vector<long long> tree(tree_size);

 

                 init(arr, tree, 1, 1, N);

 

                 cout << getMaxArea(arr, tree, 1, N) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~