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

백준의 히스토그램에서 가장 큰 직사각형(6549) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 히스토그램에서 넓이가 가장 큰 직사각형의 크기를 구해야 하는 문제이다.

먼저, 단순하게 생각해서 모든 구간에 대한 직사각형의 크기를 다 구한 후에, 최댓값을 찾아낸다면 물론 정답은 구할 수 있겠지만, 이럴 경우에는 최악의 경우 100000 * 100000 번의 연산을 진행해야 하기 때문에 주어진 시간 내에 문제를 해결할 수가 없다.

따라서 본인은 구간에 대한 연산을 빠르게 진행할 수 있는 자료구조인 세그먼트 트리를 이용해서 문제에 접근하였다.

먼저 ,이 글의 풀이를 읽기 전에 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 세그먼트 트리 알아보기(Click) ]

지금부터는 이 세그먼트 트리를 통해서 문제를 해결해보자.

#1. 세그먼트 트리에 저장할 값 설정

가장 먼저, 본인이 세그먼트 트리에 저장했던 값은 바로 "배열의 Index값"을 저장해 주었다.

배열의 Index값을 단순히 저장한 것이 아니라, 해당 구간에서 "가장 작은 높이를 가진 배열의 Index 값을 저장" 해 주었다.

왜 가장 작은 높이를 가진 배열의 값을 저장해 주었고, 왜 해당 높이가 아닌 Index값을 저장해 주었을까 ??

먼저, 배열의 Index값을 저장한 이유를 알아보자.

우리는 현재 특정 구간에서 가장 큰 직사각형의 크기를 구해야 하는 과정을 진행하고 있다.

즉, 구간을 나누기 위해서는 "현재 어디까지 탐색을 했고, 현재 점보다 더 왼쪽에 또다른 구간이 있는지, 혹은 더 오른쪽에 또 다른 구간이 있는지" 를 판단할 수 있어야 한다.

따라서 이 구간에 대한 판단을 하기 위해서 배열의 Index값을 저장해 준 것이다. 배열의 Index값을 이용한다면 이 구간에 대한 판단을 할 수 있기 때문에 배열의 Index값을 저장해 주었다.

두 번째로, 가장 작은 높이를 가진 배열을 저장한 이유를 알아보자.

위에서 말한대로라면, 본인은 세그먼트 트리에서 각 구간에 알맞은 값을 설정해줄 때, "가장 작은 높이를 가진 배열의 Index값을 저장" 했다고 했었다. 그럼 왜 가장 작은 높이를 가진 배열의 Index값을 저장을 했을까 ??

왜냐하면, 어떤 구간에서 직사각형의 크기는 해당 구간에 존재하는 "가장 작은 높이를 가진 히스토그램에 영향을 미치기 때문" 이다.

다음과 같은 상황을 생각해보자.

높이가 [ 1 , 2 , 3 , 4 , 5 ] 인 구간이 있다고 가정해보자. 이 구간에서의 직사각형의 최대 크기는 얼마가 될까 ??

( 여기서 이 구간이라는 것은, 저 1 ~ 5 를 포함하는 구간을 의미합니다. 저 안에서 또 더 작게 구간을 나눠서 구하자는 것이 아닙니다. )

이 때의 직사각형의 크기는 5가 될 것이다. 왜냐하면 가로가 5이고 세로가 1인 직사각형이 만들어 지기 때문이다.

그럼 [ 2 , 3 ] 인 구간에 대한 직사각형의 크기를 구해보자. 바로 4가 된다. 왜냐하면, 가로가 2이고 세로가 2인 직사각형이 만들어 지기 때문이다.

즉 ! 어떤 구간에서의 직사각형의 크기는, 해당 구간에 있는 "가장 작은 높이를 가진 히스토 그램에 영향"을 미치게 된다는 것이다. 따라서, 본인은 세그먼트 트리에 "각 구간에서 가장 작은 높이를 가지는 배열의 Index값을 저장" 해 주었다.

#2. 최대 넓이 구하기

넓이를 구하기 위해서는 위에서도 이야기했듯이, "구간에서의 가장 작은 높이" 를 구하는 과정이 필요하다.

구간에서의 가장 작은 높이를 구한다면, 넓이는 다음과 같이 구할 수 있다.

만약, Start 부터 End 까지의 구간에서, 구간에서의 가장 작은 높이를 구했더니 그 높이가 K 라고 가정한다면,

이 때의 직사각형의 최대 넓이는 (End - Start + 1) * K 가 된다.

물론, 여기서 주의해야 할 점이 우리는 세그먼트 트리에 "배열의 Index를 저장" 해놓았기 때문에, "구간에서의 가장 작은 높이"를 구하는 과정에서, 세그먼트 트리의 값을 그대로 return 하게 된다면, 배열의 Index를 return 받게 될 것이다.

실제로 구간에서의 가장 작은 높이는 Arr[return 받은 Index값] 이 될 것이다.

또한, 여기서 계산이 끝나는 것이 아니라 그 외의 구간들에 대해서도 계산이 필요하다.

Start 부터 End까지의 구간에서, 가장 작은 높이를 가진 배열의 Index를 구했더니 K가 나왔따고 가정해보자.

Start ~ End 까지의 구간에 대한 연산을 진행했다면,  Start ~ K - 1 , K + 1 ~ End 에 대한 계산도 필요할 것이다.

이 구간을 나누는 것 또한 우리가 Index값들을 저장해 놓았기 때문에 위와 같이 계산이 가능할 것이다.

위의 구간에서 또 그 안에서의 Left, Right 구간에 대한 연산을 재귀를 통해서 반복적으로 계산해 준 후, 최종적인 최댓값을 찾아서 도출해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100000
typedef long long ll;
using namespace std;
 
int N;
int Arr[MAX];
vector<int> Segment_Tree;
bool Inp_Flag;
 
int Min(int A, int B) { return A < B ? A : B; }
ll Max(ll A, ll B) { return A > B ? A : B; }
 
void Initialize()
{
    Segment_Tree.clear();
}
 
void Input()
{
    cin >> N;
    if (N == 0)
    {
        Inp_Flag = true;
        return;
    }
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
void Make_SegmentTree(int Node, int Start ,int End)
{
    if (Start == End)
    {
        Segment_Tree[Node] = Start;
        return;
    }
 
    int Mid = (Start + End) / 2;
    Make_SegmentTree(Node * 2, Start, Mid);
    Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    
    if (Arr[Segment_Tree[Node * 2]] <= Arr[Segment_Tree[Node * 2 + 1]]) Segment_Tree[Node] = Segment_Tree[Node * 2];
    else Segment_Tree[Node] = Segment_Tree[Node * 2 + 1];
}
 
int Find_Idx(int Node, int Start, int End, int Left, int Right)
{
    if (Right < Start || Left > End) return -1;
    if (Left <= Start && End <= Right) return Segment_Tree[Node];
    
    int Mid = (Start + End) / 2;
    int Left_Idx = Find_Idx(Node * 2, Start, Mid, Left, Right);
    int Right_Idx = Find_Idx(Node * 2 + 1, Mid + 1, End, Left, Right);
 
    if (Left_Idx == -1) return Right_Idx;
    if (Right_Idx == -1) return Left_Idx;
    if (Arr[Left_Idx] <= Arr[Right_Idx]) return Left_Idx;
    return Right_Idx;
}
 
ll Find_Area(int Start, int End)
{
    int Min_Idx = Find_Idx(1, 0, N - 1, Start, End);
    ll Result = (ll)(End - Start + 1) * (ll)Arr[Min_Idx];
    
    if (Start <= Min_Idx - 1)
    {
        ll Left_Result = Find_Area(Start, Min_Idx - 1);
        Result = Max(Result, Left_Result);
    }
 
    if (Min_Idx + 1 <= End)
    {
        ll Right_Result = Find_Area(Min_Idx + 1, End);
        Result = Max(Result, Right_Result);
    }
 
    return Result;
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    Segment_Tree.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
    ll Result = Find_Area(0, N - 1);
    cout << Result << endl;
}
 
void Solve()
{
    while (1)
    {
        Initialize();
        Input();
        if (Inp_Flag == true) return;
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}