[Algospot] 울타리 잘라내기(문제 ID : FENCE)

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

 

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

---

쿼드 트리에 이은 분할 정복 문제이다. 백준에서 비슷한 문제를 이분 탐색으로 풀었던 기억이 있지만 그 문제는 울타리의 높이에 관한 문제였고 이 문제는 넓이에 관한 문제이다. 분할하는 방법은 울타리의 처음과 끝부분에서 절반으로 자른 후 가운데에 두 울타리에서 먼저 최대 넓이를 계산한다. 그 후 연결된 양 옆의 울타리 중에서 높이가 높은 것을 차례대로 합하며 최대 넓이를 계산한다. 예를 들어 맨 처음엔 (mid, mid+1)까지를 조사한 후

(mid, mid+2), (mid-1, mid+2) 등등 순으로 점점 조사 범위를 넓히며 (1, N)까지 모든 범위를 조사하는 방식이다. 연결된 두 울타리 중 항상 높이가 더 높은 울타리를 연결하는 것이 이 문제의 키포인트이다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/FENCE.cpp

chosh95/STUDY

C++ 코드 : 

  
#include <iostream>
#include <algorithm>
using namespace std;
int C, N;
int p[20001];

int fence(int lo, int hi)
{
	if (lo == hi) return p[lo];
	int mid = (lo + hi) / 2;
	int res = max(fence(lo, mid), fence(mid + 1, hi));
	int left = mid, right = mid + 1; //경계선의 왼, 오른쪽 울타리
	int height = min(p[left], p[right]);
	res = max(res, height * 2);
	while (left > lo || right < hi) {
		if (right < hi && (left == lo || p[left - 1] < p[right + 1])) {
			++right;
			height = min(height, p[right]);
		}
		else {
			--left;
			height = min(height, p[left]);
		}
		res = max(res, height * (right - left + 1));
	}
	return res;
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 1; i <= N; i++) cin >> p[i];
		cout << fence(1, N) << endl;
	}
}