[백준(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;
}