[BOJ] 6549. 히스토그램에서 가장 큰 직사각형

 

6549번: 히스토그램에서 가장 큰 직사각형

나를 몇달동안 괴롭혔던 문제다. 처음에는 로직이 생각이 안 났고, 로직을 알고 나니 구현이 귀찮았다... 사실 귀찮아할 만큼 구현이 복잡한 문제는 아니고, 아이디어만 알면 쉽게 풀 수 있는 문제다. 아이디어 떠올리기가 너무 힘들었던 게 문제🙄..

---

세그먼트 트리 |

시간복잡도는 O(nlogn)이다.

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int N;
long long array[100001];
int segTree[300000];
 
int init(int S, int E, int index)
{
    if (S == E)
    {
        return segTree[index] = S;
    }
    else
    {
        int a = init(S, (S + E) / 2, index * 2 + 1), b = init((S + E) / 2 + 1, E, index * 2 + 2);
        return array[a] > array[b] ? segTree[index] = b : segTree[index] = a;
    }
}
 
int findMin(int S, int E, int start, int end, int index)
{
    if (S > end || E < start)
    {
        return -1;
    }
    if (S >= start && E <= end)
    {
        return segTree[index];
    }
    int a = findMin(S, (S + E) / 2, start, end, index * 2 + 1);
    int b = findMin((S + E) / 2 + 1, E, start, end, index * 2 + 2);
    if (a == -1)
    {
        return b;
    }
    else if (b == -1)
    {
        return a;
    }
    else
    {
        return array[a] > array[b] ? b : a;
    }
}
 
long long findMax(int S, int E)
{
    int mn = findMin(0, N - 1, S, E, 0);
    long long mx = (long long)(E - S + 1) * (long long)array[mn];
    if (S <= mn - 1)
    {
        mx = max(mx, findMax(S, mn - 1));
    }
    if (mn + 1 <= E)
    {
        mx = max(mx, findMax(mn + 1, E));
    }
    return mx;
}
 
int main()
{
    while (1)
    {
        cin >> N;
        for (int i = 0; i < N; i++)
        {
            cin >> array[i];
        }
        init(0, N - 1, 0);
        cout << findMax(0, N - 1) << "\n";
    }
    return 0;
}

init함수는 각 범위 별 최솟값의 위치를 세그먼트 트리에 저장한다.

findMin 함수는 지정한 범위의 최솟값의 위치를 반환한다.

중요한 건 findMax 함수인데, 이 함수는 지정한 범위 내의 가장 큰 사각형의 크기를 반환한다.

로직은 다음과 같다.

1. 범위 내의 최솟값의 위치를 구한다. 이 때 기본적으로 mx 변수에는 (범위의 길이) X (범위 내의 최솟값)이 들어간다.

2. 그 위치를 기준으로 양 옆을 나누어서 그 양 옆을 재귀로 findMax 한다.

3. (범위의 길이) X (범위 내의 최솟값)과 나눈 두 부분의 findMax 반환값을 비교해 가장 큰 값을 반환한다.

최솟값의 위치를 기준으로 두 부분으로 나누어 푸는 게 이 풀이의 핵심이다.

---

스택 |

시간복잡도는 O(n)이다.

 

(작성 중🙄)

---

같은 코드로 입력 부분만 수정해서 이 문제도 풀 수 있다.