[백준] 6549 히스토그램에서 가장 큰 직사각형

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

예제 입력 1

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

예제 출력 1

8
4000

Concept

숫자가 매우 크므로 이전 코드에서 long long으로 바꾸기로 하고, 입력 변수 값 정도만 수정하면 될 줄 알았다.

Code

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

long long fence(long long start, long long end){ 
    if (start==end) return arr[start];
    if (start+1==end){
        if (arr[start]!=0 && arr[end]!=0){ // 두 연속한 막대 모두 0이 아닐 때
            return max(max(arr[start], arr[end]), 2*min(arr[start], arr[end])); //리턴 값은 2개의 연속된 막대에 의한 것이거나, 두 막대 중 길이가 긴 한 막대. 이렇게 둘 중 하나의 값일 것이다.
        }
        else return 1*max(arr[start], arr[end]); // 길이가 0인 막대 말고 
    }
    long long mid = (start+end)/2;
    
    //case 1 & 2 : 기준(mid)의 왼쪽, 오른쪽에서만 답이 생길 경우
    long long Square1=max(fence(start, mid-1), fence(mid+1, end));
    
    
    //case 3 : 기준이 포함되어 답이 생길 경우
    long long height = arr[mid];
    long long width = 1;
    long long Square2= max(Square1, height*width);

    long long l = mid-1;
    long long 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(){
    while(1){
        long long n;
        cin>>n;
        if (n==0) break;
        for (long long i=0; i<n; i++){
            cin>>arr[i];
        }
        cout<<fence(0, n-1)<<endl;
    }
}

Comment

유사한 2문제를 풀어서 문제가 없었던 코드라 예상치 못한 '틀렸습니다'에 당황했다.
키보드를 두들겨보다가 우연히 발견한 반례로 인해

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

로 수정할 수 있었다. 가끔씩은 반례를 검색하기보단 무식한 입력이 도움이 되기도 한다는 것을 깨달았다.