[백준] 1725 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8

Concept

이 문제와 일치한다.
하지만...

Code

#include <iostream>
#include <vector>
using namespace std;
int arr[100001];

int fence(int start, int end){ // 0 6
    if (start==end) return arr[start];
    if (start+1==end) return 2*min(arr[start], arr[end]);
    
    int mid = (start+end)/2;
    
    //case 1 & 2 : 기준(mid)의 왼쪽, 오른쪽에서만 답이 생길 경우
    int Square1=max(fence(start, mid-1), fence(mid+1, end));
    
    
    //case 3 : 기준이 포함되어 답이 생길 경우
    int height = arr[mid];
    int width = 1;
    int Square2= max(Square1, height*width);

    int l = mid-1;
    int r = mid+1;
    
    //선형적으로 탐색한다. (O(n))
    while(start<=l || r <=end){
        if (start > l || (arr[l] <= arr[r] && r <= end)){ // right이 더크면
            height = min(height, arr[r]); // 오른쪽으로 넓힌다.
            r++; //그다음 index update
            width++;
            Square2 = max(Square2, width*height);
        }
        else if (r > end || (arr[l]>= arr[r] && start<=l)){ // left가 더 크면
            height = min(height, arr[l]); // 왼쪽으로 넓힌다.
            l--;
            width++;
            Square2 = max(Square2, width*height);
        }
        else break;     //왼쪽 index와 오른쪽 index가 둘 다 범위를 벗어나면 종료.
    }
    return Square2;
    
    
    
}

int main(){
    int n;
    cin>>n;
    for (int i=0; i<n; i++){
        cin>>arr[i];
    }
    // 0 1 2 3 4 5 6
    // 7 1 5 9 6 7 3
    cout<<fence(0, n-1)<<endl;
    
}

로 통과는했지만 다음 문제에서

return 2*min(arr[start], arr[end]);

부분에 문제가 있음이 드러난다.

Comment

모든 경우의 수를 생각하며 return 해야 함에 유의. 다음 문제 참고.