BOJ 1725 히스토그램

문제 링크 : https://www.acmicpc.net/problem/1725

1725번: 히스토그램

요약

히스토그램 안에서 색칠할 수 있는 직사각형의 최대 크기를 구하는 문제(한 막대그래프의 가로길이는 1로 봄) 

풀이

BOJ 2104 부분배열 고르기 문제와 유사한 문제다.
분할 정복으로 해결할 수 있으며 부분 히스토그램의 시작점을 s, 끝점을 e, 그 중간값을 mid로 두었을 때 최대 넓이는 세 가지 중에 있다. s~mid 부분 배열중 최대 넓이, mid+1~e 부분 배열중 최대 넓이, 양쪽에 걸치는 경우이다. 왼쪽과 오른쪽에서의 최댓값은 재귀호출을 통해서 구해주었고, 가운뎃 값은 중간점을 기준으로 양쪽 값 중 더 큰 쪽으로 뻗어나가면서 구해주면 된다. 높이는 부분 배열중 최솟값으로 저장해가며 넓이를 구하고 비교해주었다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, num;
vector<int> h;
int sol(int s, int e) {
	if (s == e)return h[s];
	int mid = (s + e) / 2;
	int ans = max(sol(s, mid), sol(mid+1, e));
	int l = mid;
	int r = mid + 1;
	int height = min(h[l], h[r]);
	ans = max(ans,(r - l + 1)*height);
	while (l > s || r < e) {
		if (l == s)r++;
		else if (r == e)l--;
		else {
			if (h[l - 1] > h[r + 1]) l--;
			else r++;

		}
		height = min(height, min(h[l],h[r]));
		ans = max(ans, (r - l + 1)*height);

	}

	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		h.push_back(num);
	}
	cout<<sol(0, n-1)<<"\n";
}