[Baekjoon, C++] 6549번: 히스토그램에서 가장 큰 직사각형

도입

백준 단계별 풀기에서 분할정복 아홉 번째 문제이다. 

(참고로 1725번 문제와 결을 같이한다. 1725번의 경우는 스택을 이용해 푼다.)

 

백준 6549번 문제, 입력, 출력

---

백준 6549번 입출력 예제 1

---

풀이

1. 어떤 히스토그램에서 가장 왼쪽과 가장 오른쪽을 변으로 하는 가장 큰 직사각형의 높이는? 그 히스토그램에서 가장 높이가 낮은 막대를 높이로 하는 직사각형이 가장 크다.

 

2. 그렇다면 높이가 가장 낮은 막대를 히스토그램의 왼쪽(0번째)부터 m번째 막대라고 한다면, 우리는 m의 왼쪽과 m의 오른쪽으로 나눌 수 있다. 그렇다면 하나의 히스토그램에서 임의의 n개의 히스토그램으로 분할할 수 있다. 

---

코드

#include<iostream>  
#include<vector>
#include<algorithm>

using namespace std;

typedef long long LL;

vector<LL> h; // height vector

LL calLargestSquare(int left, int right) {
    
    
    if (left == right) return h[left]; // n = 1 or end Of Div&coq
    
    int mid = (left + right) / 2;
    
    LL ret = max(calLargestSquare(left, mid), calLargestSquare(mid + 1, right));
   
    LL lo = mid;       // 젤 낮은 높이에서 좌측 (젤 낮은 높이 포함)
    LL hi = mid + 1;   // 젤 낮은 높이에서 우측
    LL height = min(h[lo], h[hi]);

    ret = max(ret, height * 2);
   
    while (left < lo || hi < right) {
        
        if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
            ++hi;
            height = min(height, h[hi]);
        }
        else {
            --lo;
            height = min(height, h[lo]);
        }
        
        ret = max(ret, height * (hi - lo + 1));
    }
    return ret;
}

int main() {
    int n, tempH;
    cin >> n;
    while (n) {
        h.clear();
        for (int i = 0; i < n; i++) {
            cin >> tempH;
            h.push_back(tempH);
        }
        cout << calLargestSquare(0, n - 1) << endl;
        cin >> n;
    }
}

---

마무리

처음 문제를 봤을 때, 감이 않왔다. 그래서 백준님의 풀이와, 여러 블로그들을 읽어보고 감을 잡았다. 점점 알아가는 과정에서 정말 재밋는 문제라는 것을 알았다.