[BOJ] 히스토그램(1725)

[백준(BOJ)] 히스토그램(1725) C++

문제 : BOJ_1725번 히스토그램

문제 설명

분할정복

유명한 분할정복 문제입니다.

스텍을 활용하여 O(N) 안에 푸는 방법도 존재한다고 들었으나, 분할정복을 이용해 풀어봤습니다.

임의의 크기를 가진 간격이 1인 막대 그리프들이 늘어져있고, 내부에서 가장 큰 넓이를 구해야 하는데

이때, 막대그래프는 연속한 막대그래프를 선택해야 하고, 높이 값은 선택된 막대그래프들 중 최소 높이, 간격은 막대그래프 하나의 간격이 1이므로, 막대그래프의 개수입니다.

---

Solution

막대그래프들을 계속 절반씩 나눠서 각각 나눠진 절반마다의 경우에서 최대 크기를 구해야 합니다.

이때, 최대 크기는 처음에 막대그래프를 중앙을 기준으로 잡고, 높이가 큰 쪽(같은 쪽이면 아무 데나)으로 확장해나가며,

확장한 모든 경우의 수마다 넓이의 최댓값을 갱신해 주며 모든 막대그래프 전체를 확장하면 분할된 구역에서 최댓값이 보장됩니다.

이때, 막대그래프를 한 번씩만 확장해 주므로 분할된 상태에서 전체 막대그래프를 탐색하는 것은 N번이고,

전체 크기를 계속 절반 씩 나누기 때문에 전체 개수가 N이라면, N이 1이 될 때까지 계속 2로 나누어 진행해야 하므로,

시간 복잡도는 O(logN * N) 임을 알 수 있습니다.

---

Description

구현이 복잡하므로, 두 개의 함수로 나눠서 풀어줬습니다.

---

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N, value[100002], area;
int printArea(int funcLeft, int funcRight);
void recursion(int le, int ri);
int main(void) {
    memset(value, -1, sizeof(value));
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> value[i];
    }
    recursion(1, N);
    cout << area << '\n';
    return 0;
}
void recursion(int le, int ri) {
    // 절반 씩 분할하는 재귀 함수
    if (le == ri) {
        area = max(area, value[le]);
        return;
    }
    area = max(area, printArea(le, ri));
    int mid = (le+ri)/2;
    if ((ri - le) == 1) {
        area = max(area, value[ri]);
        return;
    }
    recursion(le, mid);
    recursion(mid, ri);
}
int printArea(int funcLeft, int funcRight) {
    // 분할된 막대 그래프들 중 최대 넓이를 구해주는 함수
    int returnArea = 0;
    int cnt = 1;
    int mid = (funcRight + funcLeft) / 2;
    int le = mid;
    int ri = mid;
    int nowHeight = value[mid];
    bool endLe = false;
    bool endRi = false;
    while (true) {
        if (le <= funcLeft && ri >= funcRight) break;
        if (le == funcLeft) endLe = true;
        if (ri >= funcRight) endRi = true;
        cnt++;
        int nowArea;
        if (endLe) {
            ri++;
            nowHeight = min(value[ri], nowHeight);
        }
        else if (endRi) {
            le--;
            nowHeight = min(value[le], nowHeight);
        }
        else if ((value[le - 1] >= value[ri + 1]) && !endLe) {
            le--;
            nowHeight = min(value[le], nowHeight);
        }
        else {
            ri++;
            nowHeight = min(value[ri], nowHeight);
        }
        nowArea = cnt * nowHeight;
        returnArea = max(returnArea, nowArea);
    }
    return returnArea;
}