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

이 문제는 분할 정복을 이용해서 풀었다.

 

원래 세그먼트 트리로 푼다고 알고 있어서 세그먼트 트리를 만들고 있었는데, init 함수를 만들다 이미 값 계산이 끝난다는 사실을 알게 되었다.

이 문제에서 가장 핵심은 절반으로 쪼갠 mid에 걸쳐 넓이의 최댓값을 구하는 것이다.

이 부분을 해결하기 못했고, mid에서부터 좌우를 비교하여 더 높이가 높은 쪽을 선택하는 신박한 방법을 알게 되었다.

이를 통해 start ~ end까지 한번씩만 탐색하여 가운데에 걸친 넓이를 구할 수 있었다.

 

이 방식으로 해결할 경우 O(N log N) 시간이 걸릴 것으로 예측된다. 정확히 절반씩을 쪼개며 들어가므로 log N 만큼의 높이가 생기고, 각 높이에서 N개의 노드를 순회할 것이기 때문이다.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long LL;

#define MAX 100000

LL input[MAX];

int n;

LL init(int node, int start, int end) {
    if (start == end) {
        return input[start];
    }

    int mid = (start + end) / 2;

    LL left = init(node * 2, start, mid);
    LL right = init(node * 2 + 1, mid + 1, end);

    LL tempMax = input[mid];
    LL lowest = input[mid];
    
    LL tempLeft = mid;
    LL tempRight = mid;
    
    while (true) {
        if (tempLeft == start && tempRight == end) {
            break;
        }

        if (tempLeft - 1 < start) {
            tempRight++;
            lowest = min(lowest, input[tempRight]);
        } else if (tempRight + 1 > end) {
            tempLeft--;
            lowest = min(lowest, input[tempLeft]);
        } else {
            if (input[tempLeft - 1] >= input[tempRight + 1]) {
                tempLeft--;
                lowest = min(lowest, input[tempLeft]);
            } else {
                tempRight++;
                lowest = min(lowest, input[tempRight]);
            }
        }

        int length = tempRight - tempLeft + 1;
            
        tempMax = max(tempMax, length * lowest);
    }

    return max(tempMax, max(left, right));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    while (true) {
        cin >> n;

        if (n == 0) {
            break;
        }

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

        LL result = init(1, 0, n - 1);

        cout << result << '\n';
    }

    return 0;
}