[C++][백준] 1725 히스토그램

이 문제는 분할 정복을 활용해서 해결하는 문제이다.

 

 

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.
각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.
이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.
주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

 

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

 

어떻게 해결해야 할까?

• 가장 단순하게 생각하면 선형적으로 비교해가면서 모든 히스토그램을 계산하면 답을 구할 수는 있을 것이다.
• 그러나 이런 방법으로는 절대 제한시간 0.7초 이내에 문제를 해결할 수는 없다.

배열을 절반으로 나누어서 가운데를 기준으로 분할하면서, 크기를 가장 크게 유지하는 방향으로 옆으로 늘리는 방법을 사용하면 어떨까?

어차피 절반으로 배열을 분할하는 과정을 재귀적으로 잘 반복하면 전체 크기n 부터 n/2, n/4, ... 1의 크기를 갖는 히스토그램을 모두 고려할 수 있을 것이다.

코드를 살펴보자

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll merge(ll A[], ll start, ll end)
{
    if(start > end) return 0;
    if(start == end) return A[start];
    ll mid = (start+end)/2;
    ll Large = A[mid], len = 1, height = A[mid];
    ll i = mid-1, j = mid+1;
    while(start <= i && j <= end)
    {
        if(A[i] > A[j])
        {
            len++;
            height = min(height,A[i--]);
        }
        else {
            len++;
            height = min(height,A[j++]);
        }
        Large = max(Large,height*len);
    }
    while(start <= i)
    {
        len++;
        height = min(height,A[i--]);
        Large = max(Large,height*len);
    }
    while(j<=end)
    {
        len++;
        height = min(height, A[j++]);
        Large = max(Large,height*len);
    }

    Large = max(Large, merge(A,start,mid-1));
    Large = max(Large, merge(A,mid+1,end));
    return Large;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    cin >> N;
    ll arr[N];
    for(ll i=0; i<N; i++)cin  >> arr[i];
    cout << merge(arr,0,N-1);
    return 0;
}

• merge라는 함수를 선언해주었다.
• merge함수는 배열 범위를 start와 end의 중간지점인 mid를 기준으로 두 배열로 나누고 현재 배열의 크기에서 가장 큰 크기를 구하는 재귀함수이다. 
• i는 mid를 기준으로 작은쪽으로, j는 mid를 기준으로 큰 쪽으로 인덱스를 이동하면서 더 높이를 크게 유지할 수 있게 하면서, 가장 큰 Large값을 저장한다.
• 병합정렬과 똑같이 한쪽 인덱스가 범위를 초과하게 되면 나머지 범위 안에 있는 인덱스를 끝까지 이동시키면서 해당 범위에서의 최대 Large값을 구한다.