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

링크: https://www.acmicpc.net/problem/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이 하나 주어진다.

출력

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

---

풀이

히스토그램에서 가장 큰 직사각형을 구해야 하는 문제이다.

그런데 가능한 종류의 직사각형이 매우 많기 때문에, 이들의 넓이를 모두 구한 뒤 가장 큰 것을 찾는 것은 매우 비효율적이다.

따라서 적절한 자료구조, 또는 풀이 방법을 통해 효율적으로 정답을 찾을 수 있도록 해야 한다.

 

이 문제는 분할 정복, 세그먼트 트리, 스택 등을 활용해 풀 수 있다.

나는 문제를 처음 보았을 때 위 방법들 중 분할 정복을 활용한 풀이를 떠올렸고, 그 방법을 활용한 풀이는 다음과 같다.

(사실 세그먼트 트리와 접근 및 풀이 과정은 매우 비슷하다.)

만약 분할 정복을 잘 모른다면, 이를 활용하는 대표적인 사례인 병합 정렬(Merge Sort)을 찾아보는 것을 추천한다.

 

 

예제 1에 해당하는 히스토그램이 다음과 같이 있다.

 

1~7 중 가장 큰 직사각형을 구하기 위해서, 1~4 중 가장 큰 직사각형과 5~7 중 가장 큰 직사각형을 구한다.

 

1~4 중 가장 큰 직사각형을 구하기 위해서, 1~2 중 가장 큰 직사각형과 3~4 중 가장 큰 직사각형을 구한다.

 

1~2 중 가장 큰 직사각형을 구하기 위해서, 1과 2 중 가장 큰 직사각형을 구한다.

1의 넓이가 2로 더 크며, 1~2 중 가장 큰 직사각형은 2이다.

 

3~4 중 가장 큰 직사각형을 구하기 위해서, 3과 4중 가장 큰 직사각형을 구한다.

4의 넓이가 4로 더 크며, 3~4 중 가장 큰 직사각형은 4가 아닌 노란색 영역인 8이다.

 

위 3~4에서 중요한 부분이 등장하는데, 단순히 왼쪽 오른쪽으로 구간을 나눠서 leftMax값과 rightMax값을 비교하는 것은 옳지 않다.

왼쪽 구간과 오른쪽 구간에 걸쳐 있는, 중간 구간에 가장 큰 직사각형이 존재할 수 있기 때문이다.

따라서 3번을 l, 4번을 r이라 했을 때 구간 내에서 l을 왼쪽으로, r을 오른쪽으로 확장해보며 가능한 직사각형 넓이들을 조회해주어야 한다.

즉 3~4 중 가장 큰 직사각형의 넓이는 왼쪽 구간 4, 오른쪽 구간 5, 가운데 구간 8 중 가장 큰 값인 8이다.

 

다시 돌아와 1~4 중 가장 큰 직사각형을 구해보자.

왼쪽 구간에서 최댓값은 2, 오른쪽 구간에서 최댓값은 8이었고

2와 3을 포함하는 중간 구간에서의 최댓값은 4이다. (1 * 4 사이즈)

따라서 1~4 중 가장 큰 직사각형의 넓이는 8이다.

 

위 방법으로 최초 히스토그램을 분할하여 구간별로 가장 큰 직사각형 넓이를 구하고, 정복해나가면 위 문제를 풀 수 있다.

코드

#include <iostream>
#include <vector>
typedef unsigned long long ull;
using namespace std;

int heights[100001];

ull solve(int left, int right){
    if (left == right){
        return heights[left];
    }
    int mid = left + (right - left) / 2;
    
    // 왼쪽 구간과 오른쪽 구간에서 가장 큰 직사각형 넓이 구하기
    ull leftMax = solve(left, mid);
    ull rightMax = solve(mid+1, right);

    // 중간 구간: 경계를 기준으로 좌우로 넓혀가며 넓이 구하기
    int l = mid;
    int r = mid+1;
    int minH = min(heights[l], heights[r]);
    ull middleMax = 2 * minH;
    while (left <= l && r <= right){
        minH = min(min(heights[l], heights[r]), minH);
        middleMax = max(middleMax, ull(r-l+1)*minH);

        int ll = 0, rr = 0;
        if (left <= l-1){
            ll = heights[l-1];
        }
        if (r+1 <= right){
            rr = heights[r+1];
        }

        if (ll == 0 && rr == 0){
            break;
        }
        else if (ll < rr){
            r++;
        }
        else{
            l--;
        }
    }
	
    // 왼쪽, 오른쪽, 중간 구간 중 가장 큰 값을 리턴
    return max(max(leftMax, rightMax), middleMax);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);


    while (true){
        int n;
        cin >> n;
        if (n == 0){
            break;
        }

        for (int i = 1; i <= n; i++){
            cin >> heights[i];
        }

        ull answer = solve(1, n);
        cout << answer << "\n";
    }
}