백준[1725] 히스토그램

https://www.acmicpc.net/problem/1725

 

입력이 10만이라, O(N^2)은 시간 내 풀이가 불가능합니다.

 

"이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야한다." 에서 아래쪽 밑변은 히스토그램의 아랫변과 겹치게 그리는 것이 항상 최대이고, 위쪽 밑변은 직사각형이 포함하는 막대들의 높이 중 최소인 막대의 윗변과 겹쳐야합니다.

 

O(NlogN)가 걸리는 분할정복으로 풀어봤습니다.

하나의 히스토그램을 절반으로 잘라서 왼쪽의 최대와 오른쪽의 최대, 그리고 중간을 포함하는 큰 히스토그램의 최대를 구하여 비교합니다.

중간을 포함하는 큰 히스토그램은 투 포인터로 O(N)이 걸립니다.

 

left와 right를 각각 mid, mid+1로 초기화 하고 left-1, right+1의 높이를 비교하여 큰 쪽으로 확장하면서 넓이를 구합니다. 그리고 각각 구한 넓이의 최대값을 구합니다.

 

좀 더 자세히 설명하자면,

인덱스가 mid, mid+1인 두 막대를 포함하는 넓이를 구하기 때문에 직사각형의 확장은 왼쪽 혹은 오른쪽으로밖에 하지 못 합니다.

이 때 왼쪽이나 오른쪽 어디로 확장해야하는지 선택해야하는데, 그 전에 직사각형의 넓이는 밑변*높이 입니다. 왼쪽 혹은 오른쪽 확장은 둘 다 밑변이 1 증가하므로 높이가 최대한 줄어들지 않는 쪽으로 선택해야한다. 즉, left - 1과 right + 1의 높일를 비교하여 더 높은쪽을 선택하여 확장해야합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#define lld long long

using namespace std;

int n;
vector<int> v;

lld solve(int start, int end) {
	if(start == end) {
		return v[start];
	}
	if(start > end) {
		return 0;
	}

	int mid = (start + end) / 2;
	lld left_area = solve(start, mid); // 왼쪽 히스토그램
	lld right_area = solve(mid + 1, end); // 오른쪽 히스토그램
	lld mid_area = 0;

	lld max_area = max(left_area, right_area);

	int left = mid;
	int right = mid + 1;
	int height = min(v[left], v[right]);
	mid_area = (right-left+1) * height;
	
	// 중간(mid, mid+1) 두 개의 막대를 포함하는 가장 큰 넓이. 어느 한 쪽이 끝에 도달할때까지 반복
	while(start < left && right < end) {
		if(v[left-1] < v[right+1]) {
			right++;
			height = min(height, v[right]);
		} else {
			left--;
			height = min(height, v[left]);
		}
		lld area = (right-left+1) * height;
		mid_area = max(mid_area, area);
	}

	lld area = 0;
    // 왼쪽 혹은 오른쪽에 먼저 도달했을 경우 반대편을 끝까지 확장하기
	if(start == left) {
		while(right < end) {
			right++;
			height = min(height, v[right]);
			area = (right-left+1) * height;
			mid_area = max(mid_area, area);
		}
	} else {
		while(left > start) {
			left--;
			height = min(height, v[left]);
			area = (right-left+1) * height;
			mid_area = max(mid_area, area);
		}
	}
	return max(mid_area, max_area);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	v = vector<int>(n);
	for(int i = 0; i < n; i++) {
		cin >> v[i];
	}
	lld ans = solve(0, n-1);
	cout << ans << endl;

	return 0;
}