04.03. 히스토그램[Divide and conquer][백준 1725]

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

1629번: 곱셈

 

Algorithm classification : Divide and conquer, Stack, Data structure

 

04.03.1. Problem

I am trying to draw a rectangle with the largest area inside the histogram. The shaded area in the figure below is an example. The base of this rectangle should always be drawn parallel to the lower edge of the histogram.

For a given histogram, write a program to find the area of ​​the largest rectangle.

 

04.03.2. Input limit

The first row is given N (1 ≤ N ≤ 100,000). N is the number of horizontal columns in the histogram. Over the next N rows, the height of each cell is given sequentially from left to right. The height of each cell is a natural number less than or equal to 1,000,000,000 or zero.

 

04.03.3. Output

Print the area of ​​the largest rectangle on the first line. This value does not exceed 2 billion.

 

04.03.4. Solution

매우 유명한 문제입니다. 제가 알기로는 풀이가 굉장히 다양한 것으로 알고 있습니다. 앞서 포스팅한 부분배열 고르기 문제의 code를 잘 활용하시면 됩니다. 물론 구해야 하는 값이 다르기 때문에 return value를 계산하는 부분은 달라질 것입니다. 하지만 핵심 아이디어는 같습니다. 

 

직사각형 갯수를 보시면 N이 작은 값은 아닙니다. 따라서 O(N^2)으로는 조금 힘들어보이고 O(NlogN)정도는 되어야 풀릴겁니다. 사실 분할정복이라는 것을 눈치채신 이상 O(NlogN)정도로 구현을 해주셔야 합니다. 알고리즘 분류에 Stack도 있는데 stack을 사용하면 시간복잡도를 조금 더 낮쳐줄 수 있겠군요.(아주 이상한 code를 짜지 않는 이상 기본적으로 추가적인 data structure을 사용하면 시간복잡도는 낮아지는 것이 정상입니다.)

 

다시 한번 아이디어를 되짚자면 분할한 지점을 답이 포함할 수도 있다는 것입니다. 정복(conquer or merge)단계에서 이 경우를 잘 처리해 주어야 한다는 것이죠. 양 옆으로 확장해가면서 확인해나가는 logic을 구현하면 될 겁니다. 이 logic 자체는 size만큼만 확장하면서 확인할 것이므로 O(N)이라는 것을 쉽게 알 수 있습니다. 즉, 시간복잡도를 계산할 때 sub항이 되는거죠.(간혹 sub항도 무시할 수 없을 정도일 수 있습니다.) 이론에서 소개해드린 Master Theorem에 대입한다면 a = 2, b = 2, d = 1이겠군요.(이 경우 시간복잡도는 O(NlogN)입니다.)

 

long long int cal(int s, int e){
	if(s == e) return datab[s];
	//if(s+1 == e) return 2 * min(datab[s], datab[e]);
	int mid = (s+e) / 2;
	long long int result;
	
	result = max(cal(s, mid), cal(mid+1, e));	
	long long int temp, mintemp;
	int i, j, k;
	i = mid; j = mid+1;
	mintemp = min(datab[i], datab[j]);
	temp = 2;
	result = max(result, mintemp*temp);
	while(s <= i && j <= e){
		if((s == i && j <= e + 1) || (j <= e + 1 && s + 1 <= i && datab[i-1] < datab[j+1])){
			temp ++;j++;
			mintemp = min(mintemp, (long long)datab[j]);
		}
		else if(s+1 <= i){
			temp ++;i--;
			mintemp = min(mintemp, (long long)datab[i]);
		}
		result = max(result, mintemp*temp);
		//printf("%d %d %d\n",i, j, result);
	}

	return result;
}

처음에는 이렇게 시도해볼 수도 있습니다. 물론 for문을 보시면 시간초과가 걸리겠구나라는 생각이 드실겁니다.

	if(s != e){
		for(i = s; i <= e; i++){
			for(j = i; j <= e; j++){
				mintemp = 1,000,000;
				temp = 0;
				for(k = i; k <= j; k++){
					//temp += datab[k];
					temp++;
					mintemp = min(mintemp, datab[k]);
				}
				result = max(result, temp*mintemp);
			}
		}	
	}