[백준] 1725번 히스토그램 & [프알문] 울타리 잘라내기

이번 문제는 1725번 히스토그램인데, 프알문의 울타리 잘라내기 문제와 풀이 방식이 똑같아 포스팅하였습니다.

울타리 잘라내기와 마찬가지로 이 문제를 브루트포스로 접근하게 되면 시간복잡도가 너무 높으므로 분할 정복으로 접근하였습니다.

 지금부터 울타리를 반으로 쪼개며, 확장을 하면서 분할 정복을 할 것입니다. 먼저 기저사례를 기본적인 분할 정복에서의 기저사례와 같은 left==right일시 기본 높이 값을 반환해주며, 그 후 left~mid, mid+1~right로 나누어 계산을 할 것입니다.

 먼저 반으로 쪼개가며 확장을 시키면 모든 케이스를 확인 할 수 있습니다. 그렇기 때문에 반으로 쪼개가는 것이고, 확장을 시킬 때 왼쪽으로 갈지 오른쪽으로 갈지는 더 높은 케이스를 찾아가도록 설정을 해주었습니다.

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> h;


int hisGram(int left, int right) {
	if (left == right) {
	
		return h[left];
	}
	int mid = (left + right) / 2;
	int ret = max(hisGram(left, mid), hisGram(mid + 1, right));
	//겹치는 경우
	int lo = mid; int hi = mid + 1;
	int height = min(h[lo], h[hi]);
	ret = max(ret, height * 2);
	//겹치고 나서 확장을 하자
	while (left < lo || right > hi) {
		if (hi < right && (left == lo || (h[lo - 1] < h[hi + 1]))){
			++hi;
			height = min(height, h[hi]);

		}
		else {
			--lo;
			height = min(height, h[lo]);
		}
		ret = max(ret, height*(hi - lo + 1));
	}
	return ret;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; ++i) {
		int tmp;
		cin >> tmp;
		h.push_back(tmp);
	}
	int ret = hisGram(0, h.size()-1);
	cout << ret;


}