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

문제

접근 방법

앞선 두 세그먼트 트리 문제를 풀고 난 뒤 한번 어려운 문제를 풀어보고 싶어서 골라봤다.
시작점, 끝점, 높이, 너비를 가지는 객체를 재귀적으로 불러내어 5가지 경우로 나뉘어 반환하려 했다. (지금 생각해보니 끝점과 너비 둘 다 해둘 필요는 없던 것 같다)

1. 이어져 있는 경우
   1.1 높이가 작은 것의 넓이가 더 큰 경우
   1.2 높이가 같은 경우
   1.3 높이가 큰 것의 넓이가 더 큰 경우
2. 이어져 있지 않은 경우
   2.1 높이가 작은 것의 넓이가 더 큰 경우
   2.2 높이가 큰 것의 넓이가 더 큰 경우

1.1, 1.2의 경우는 합쳐서 반환하고 나머지 경우는 더 큰 것을 반환하려 했다.

하지만 이렇게 하면 구간이 나누어졌을 때 1, 2, 3, 4, 5의 경우도 있기에 오답이 나왔다. (위에 내용대로 하면 가장 처음 재귀가 끝났을 때 2, 4, 5가 남는데 3, 4, 5가 이어진 경우가 9가 나와서 가장 크다. 하지만 2, 4, 5로는 만들어질 수 없기에 8이라는 오답이 나온다)

찾아보니 높이가 가장 작은 경우부터 해결하는 방식으로 분할정복을 하면 되는 것을 알게 됐다.
1, 2, 3, 4, 5의 경우 높이가 1인 경우부터 시작하는 것이다.
3, 2, 1, 2, 3인 경우에도 가장 작은 높이인 1부터 시작하고 그 뒤 1을 제외한 양옆에서 가장 작은 높이인 2를 고르는 것이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
int n;
ull numArr[100000], tree[400000], ret;
int init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = start;
    int mid = (start + end) >> 1, nextNode = node << 1;
    int l = init(start, mid, nextNode);
    int r = init(mid + 1, end, nextNode | 1);
    return tree[node] = (numArr[l] < numArr[r] ? l : r);
}
ull find(int start, int end, int node, int left, int right)
{
    if (start > right || end < left)
    {
        return 100000;
    }
    if (start >= left && end <= right)
    {
        return tree[node];
    }
    int mid = (start + end) >> 1;
    int nextNode = node << 1;

    int leftIdx = find(start, mid, nextNode, left, right);
    int rightIdx = find(mid + 1, end, nextNode | 1, left, right);

    if (leftIdx == 100000)
        return rightIdx;
    else if (rightIdx == 100000)
        return leftIdx;
    else
        return numArr[leftIdx] < numArr[rightIdx] ? leftIdx : rightIdx;
}
void sizeFind(int start, int end)
{
    if (start > end)
        return;
    int idx = find(0, n - 1, 1, start, end);
    ret = max(ret, numArr[idx] * (end - start + 1));
    sizeFind(start, idx - 1), sizeFind(idx + 1, end);
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    while (true)
    {
        cin >> n;
        if (n == 0)
            return 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> numArr[i];
        }
        ret = 0;
        init(0, n - 1, 1);
        sizeFind(0, n - 1);
        cout << ret << "\n";
    }
}

풀이

세그먼트 트리에 인덱스를 저장할 수 있는가와 분할 정복을 활용할 수 있는가를 시험하는 문제였던 것 같다.

쉽게 풀 수 있을 거로 생각했는데 결국 다른 사람의 풀이를 봐버렸다. 잘못된 방식에 매몰됐던 것 같다.
백준 기록상으로 100번째 문제이기에 더 아쉬웠던 것 같다. (옛날에 연습 삼아 풀었던 것들은 velog에 안 올라왔다)