[BOJ 1725] 히스토그램

문제 출저 : https://www.acmicpc.net/problem/1725

 

풀이 : 

 

스택으로도 풀 수 있고, 분할 정복으로도 풀 수 있는 문제입니다.

스택으로는 아직 안 풀어 봐서 다음에 기회가 되면 올리도록 하고 분할 정복으로 설명하겠습니다.

이 문제는 분할 한 두 영역에 겹쳐서 최댓값이 존재 할 수도 있기 때문에 병합을 할 때

매번 중앙부터 시작해 양 옆으로 확장 해 나가면서

현재 구해진 값 과 중간 값 중 최댓값을 찾는 과정을 병행 해주어야 합니다.

그 과정은 중앙에서 부터 양옆으로 탐욕적으로 넓혀 나가시면 됩니다.

#include<stdio.h>
#include<algorithm>
using namespace std;
 
int n, arr[100000];
 
int divide(int s,int e)
{
    if (s + 1 == e)return arr[s];
    if (s == e)return 0;
    int ret = 0;
    int mid = (s + e) / 2;
    ret = max(divide(s, mid), divide(mid, e));
 
    int h=arr[mid],l =mid,r = mid;
    while (r- l + 1 < e - s)
    {
        int p = l > s ? arr[l - 1] : -1;
        int q = r < e - 1 ? arr[r + 1] : -1;
 
        if (p >= q)
        {
            if (h > p)h = p;
            l--;
        }
        else
        {
            if (h > q)h = q;
            r++;
        }
        ret = max(ret, (r - l + 1)*h);
    }
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)scanf("%d", &arr[i]);
    printf("%d",divide(0, n));
}