[BOJ] 1725번 : 히스토그램

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

 

divide and conquer로 해결할 수 있는 문제이다. 

 

start에서 end까지의 부분 히스토그램을 보았을 때, 그 안에서 만들 수 있는 직사각형의 최대 넓이는 세 경우 중 하나에서 구할 수 있다. 편의상 mid = (start+end)/2 로 정의한다.

 

1. start ~ mid까지의 부분 히스토그램 중 최대 넓이

2. mid+1 ~ end까지의 부분 히스토그램 중 최대 넓이

3. mid와 mid+1을 포함하는 부분 히스토그램 중 최대 넓이(중간에 걸쳐 있는 것)

 

1과 2는 재귀로 구하면 되고, 3번이 문제인데, 3번은 가운데 두 막대그래프에서 시작해서 하나씩 확대해가면서 최대 넓이를 갱신하면 된다. 맨 처음 min(h[mid], h[mid+1])을 height로, 2를 width로 두어 넓이를 계산하여 최대 넓이로 설정한다. 그 다음 left-1과 right+1을 확인하여 더 높이가 높은 쪽으로 한 칸 확장시켜 다시 넓이를 확인하면 된다.

 

이것이 가능한 이유는 높이가 더 높은 쪽으로 확장시키는 쪽이 항상 더 넓은 넓이를 확인할 수 있게 해 주기 때문이다. 만약 높이가 더 낮은 쪽으로 하는 것이 최종적으로 더 넓은 넓이가 되더라도, 그 쪽은 나중에 계산해도 그 값을 얻을 수 있다. 높은 쪽을 먼저 다 하고 나서 낮은 쪽으로 오면 되기 때문이다.

 

시간복잡도는 3번이 단계마다 N번 소요되고, level이 logN개 있으므로 NlogN이다.

 

 

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
const int maxN = 100500;
 
int c, n, h[maxN];
 
int maxMidCross(int start, int end) {
    
    int maxArea = -1;
    int mid = (start+end)/2;
    int left = mid;
    int right = mid+1; 
    int height = min(h[left], h[right]);
    maxArea= (right-left+1)*height;
    
    while(left > start || right < end) {
        
        if(left == start) right++;
        else if(right == end) left--;
        else {
            if(h[left-1] > h[right+1])    left--;
            else right++;
        }
        height = min(height, h[left]);
        height = min(height, h[right]);
        maxArea = max(maxArea, (right-left+1)*height);
        
        
    }
    
    return maxArea;
    
}
 
int maxRect(int start, int end) {
    
    int maxArea = -1;
    int mid = (start+end)/2;
    if(start==end) return h[start];
    
    else { 
        
        maxArea = max(maxArea, maxRect(start, mid));
        maxArea = max(maxArea, maxRect(mid+1, end));
        maxArea = max(maxArea, maxMidCross(start, end));
        
    }
    return maxArea;
    
}
 
int main ( void )  {
    
    scanf("%d", &n);
    for(int j = 0; j < n; j++) {
        scanf("%d", &h[j]);
    }
        
    printf("%d\n", maxRect(0, n-1));
 
    
}