[BAEKJOON 1725번] (C++) 히스토그램

 

www.acmicpc.net/problem/1725

1725번: 히스토그램

분할정복을 통해 문제를 해결하였다.

문제에서 middle(중단점) 을 기준으로 히스토그램을 나누었을 때 최대값이 나올 수 있는 경우는 세가지이다.

1. middle을 중심으로 왼쪽부분에 최대값이 있는 경우

2 middle을 중심으로 오른쪽부분에 최대값이 있는 경우

3. middle을 포함하여 직사각형을 이루고 있는 경우

 

한 기둥을 중심으로 최대값의 넓이를 계산하기 위해서는 더 높은 막대로 확장해나가면서 최대값과 비교하여 최종적으로 최대값을 구한다.

 

세가지 경우에 대하여 각각 최대값을 구하고 그 중 가장 큰 값을 출력한다.

 

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int a[100001];

int maxSize(int start, int end) {
	if (start == end)return a[end];

	int mid = (start + end) / 2;
	int lo = mid, hi = mid + 1;
	int height = min(a[lo], a[hi]);
	int ret = height * 2, tmp;

	//start와 end를 기준으로 조건에 따라
	//한쪽 끝에 도달했을 경우 종료
	while (start < lo || hi < end) {
		if (start == lo) tmp = ++hi;
		else if (hi == end) tmp = --lo;
		//더 큰쪽으로 확장을 진행한다.
		else if (a[lo - 1] < a[hi + 1]) tmp = ++hi;
		else tmp = --lo;
		//1칸씩 확장하면서 현재까지의 최대값을 ret에 저장
		height = min(height, a[tmp]);
		ret = max(ret, height * (hi - lo + 1));
	}

	//1. 가운데에 걸치는 부분 배열, 2. 왼쪽 부분 배열 3. 오른쪽 부분 배열
	//세가지중 가장 큰 값을 return 한다.
	return max(ret, max(maxSize(start, mid), maxSize(mid + 1, end)));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i)cin >> a[i];
	cout << maxSize(0, n - 1);
}