[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;
}