[C/C++] 백준 #1725 히스토그램(분할 정복)

히스토그램 문제는, 히스토그램 그래프에서 x축의 빈도의 너비와, y축의 값의 높이 단위 크기가 같을때, 히스토그램 그래프 안에 직사각형의 넓이가 최대가 되는 것을 구하는 문제입니다.

 

분할정복 문제의 전형적인 경우입니다.

 

예를 들어서 히스토그램의 값이 [ 3, 2, 3, 4, 2, 3, 4, 1 ]의 값을 가진다고 하면, 이를 히스토그램으로 표현하면 아래와 같습니다.

 

histogram

 

사람이 본다면 인지적으로 높이 2인 직사각형이 가장 넓을 것이라 할 수 있습니다.  하지만, 히스토그램의 x축 개수가 매우 많다면 사람이 인지적으로 판단하는 것도 힘듭니다.

 

컴퓨터가 푼다면,

높이 1인 것부터 차례로 찾아볼 수도 있습니다.

히스토그램의 1보다 큰 수가 얼마나 연속되었는지 찾으면 됩니다.  이것이 \(O(N)\) 알고리즘이니, 높이의 개수를 히스토그램의 분포의 개수와 연관된다고 가정하면 \(O(N^2)\) 알고리즘이 됩니다. 

 

그 외의 방법으로는 구간을 정해서 그 안에 최소의 빈도값과 구간의 그래프 개수와 곱한 값의 최대값을 찾는 방법도 있습니다.

 

\[ r = max( min(a_i, a_{i+1}, ..., a_{j}) \times (j-i+1) ~ for~ all~ i \le j ) \]

 

이 방법 역시 \(O(N^2)\) 알고리즘이 됩니다.

 

위의 구간을 구하는 방법을 보시면, 정렬 알고리즘과 비슷해 보입니다.  분할정복을 이용하면, \(O(N \log N)\) 알고리즘이 가능해 보입니다.

Divide and Conquer

 

제가 사용한 알고리즘은 위의 그림과 같이 중위값을 기준으로 두 부분으로 나눕니다.  그러면 최대 넓이의 직사각형은 파란선을 기준으로 왼쪽에서 나오거나, 오른쪽에서 나오거나, 아니면 파란선을 공유하는 두개의 그래프를 반드시 포함하는 곳에서 나옵니다.

 

Histogram merge

위 그림의 두개의 빨간 히스트그램 그래프는 분할선을 포함하는 두개의 그래프입니다.  이 두개를 반드시 포함해야 하므로 최소값을 구합니다.

 

\[ minv = min(a_c, a_{c+1}) \]

 

이 최소값을 이용해서 현재 넓이를 구하고, 왼쪽과 오른쪽의 그래프값 중 큰 값을 선택해서 늘려 나갑니다.  큰 값을 선택해야 하는 이유는 최대 넓이의 직사각형을 구하기 위해서는 현재 선택된 그래프 중 최소값을 구하기때문입니다.

 

이렇게 늘려 나가면, 중앙의 빨간 그래프 두개를 포함한 최대 넓이의 직사각형을 얻을 수 있습니다.  알고리즘 과정은 합병 정렬(merge sort)의 합병(merge) 과정과 유사합니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.  (참고로 #1725, #6549는 같은 문제입니다.)

//----------------------------------------------------------
//  baekjoon #1725 - Histogram
//      - by Aubrey Choi
//      - created at 2020-01-25
//----------------------------------------------------------
#include <stdio.h>

int n, v[100000];
long long min(long long a, long long b) { return a<b?a:b; }
long long max(long long a, long long b) { return a>b?a:b; }
long long dnc(int s, int e)
{
    if(s+1==e) return v[s];
    if(s+2==e) return max(max(min(v[s],v[s+1])*2,v[s]),v[s+1]);
    int c=(s+e)/2;
    int i=c-2, j=c+1;
    long long r=min(v[c-1],v[c]), m=r*2;
    while(s<=i && j<e)
    {
        r=min(v[i]<v[j]?v[j++]:v[i--],r);
        m=max(r*(j-i-1),m);
    }
    while(s<=i)
    {
        r=min(v[i--],r);
        m=max(r*(j-i-1),m);
    }
    while(j<e)
    {
        r=min(v[j++],r);
        m=max(r*(j-i-1),m);
    }
    return max(m, max(dnc(s,c), dnc(c,e)));
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",v+i);
    printf("%lld\n",dnc(0,n));
}