[백준] 히스토그램에서 가장 큰 직사각형 (c++) 분할 정복

출처 : https://www.acmicpc.net/problem/6549

 

풀이 방법

대표적인 분할 정복의 문제이다.

왼쪽에서 가장 큰 사각형, 오른쪽에서 가장 큰 사각형, 경계 지역 사각형을 포함하는 사각형 중 가장 큰 사각형을 찾으면 된다.

 

 

가장 중요한 부분은 경계 지역을 포함하는 사각형의 최대 크기이다.

주의 히스토 그램이 위와 같을 때 파란색 부분과 검은색 부분도 while문을 사용해 다 계산을 해주어야 한다.

 

기저 조건으로 start == end, end - start == 1인 경우로 설정했다.

 

실수한 점 

넓이는 long long을 사용했다. 

하지만 밑변과, 높이는 int이였다.

long long width = height * (end - start)

위와 같이 식을 작성했는데 연산 순서가 int끼리의 연산 후 long long변수에 할당하는 것이므로 int끼리 계산할 때 먼저 오버플로우가 발생한다.

long long width = (long long) height * (end -start)로 작성해 주어야 한다.

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;


long long width;
vector<int> height;


void input(int n) {
    height.clear();
    int num;
    for (int i = 0;i < n;i++) {
        cin >> num;
        height.push_back(num);
    }
    return ;
}

long long divide_conque(int start, int end) {     
    long long ret = 0;
    if (start == end) { // 길이가 1        
        return height[start];
    }
    if (end - start == 1) { //길이가 2
        return max(min(height[start], height[end]) * 2, max(height[start], height[end]));
    }

    int mid = (start + end) / 2;

    ret = max(ret, divide_conque(start, mid)); // 왼쪽
    ret = max(ret, divide_conque(mid + 1, end)); // 오른쪽
    // 중간        
    int left = mid-1, right = mid+1;
    int now_height = height[mid];
    long long mid_area = height[mid];
    while (left >= start && right <= end) {
        if (height[left] < height[right]) {
            if (height[right] < now_height) {
                now_height = height[right];
            }            
            long long next_area = (long long) now_height * (right - left);
            mid_area = max(mid_area, next_area);
            right++;
        }

        else {
            if (height[left] < now_height) {
                now_height = height[left];
            }
            long long next_area = (long long) now_height * (right - left);
            mid_area = max(mid_area, next_area);
            left--;
        }
    }
    // 왼쪽으로
    while(left >= start) {    
        if (height[left] < now_height) {
            now_height = height[left];
        }                
        long long next_area = (long long) now_height * (right - left);
        mid_area = max(mid_area, next_area);
        left--;
    }
    // 오른쪽으로
    while (right <= end) {     
        if (height[right] < now_height) {
            now_height = height[right];
        }        
        long long next_area = (long long) now_height * (right - left);
        mid_area = max(mid_area, next_area);
        right++;
    }    
    ret = max(ret, mid_area);    
    return ret;
}

void sol() {    
    cout << divide_conque(0, height.size()-1) << endl;
}

int main() {

    string str;

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

    return 0;
}