문제

출처 : https://www.algospot.com/judge/problem/read/FENCE

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

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

입력

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

출력

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

풀이(책 참고)

가장 먼저 시도한 방법은 총 n개의 성분에 대해 가로 길이를 x라 할 때, 연속된 x개의 울타리에서 최대 넓이를 구하여, x가 1부터 n까지의 경우를 모두 비교하여 최대 넓이를 계산하도록 생각하였다. 연속된 x개의 울타리의 최대 넓이의 경우, x개중 울타리의 최소 높이를 비교하여 찾아 최소 높이와 가로 길이인 울타리 개수 x를 곱하여 넓이를 계산하고, 시작 위치에서 x개를 연속하여 이때의 넓이들을 각각 모두 비교한다.

이 방식의 경우, 1개부터 n개까지의 경우를 계산하고, 각각의 경우에 대해서도 시작성분부터 끝성분까지 최대 넓이를 비교하여야 하므로 시간복잡도가 O(n^2)으로 오랜 시간이 걸린다. 그래서 분할 정복으로 풀이하려고 시도하였지만, 문제를 어떤 식으로 분할하여야 하는지 쉽게 알 수 없었다.

단순히 울타리의 전체 부분에서 절반으로 나누어 분할하는 방식을 생각해보았는데, 이 경우 분할된 두 울타리에서 최대 넓이가 각 울타리를 걸쳐서 나오는 경우를 생각하지 못하기 때문에 불가능하다고 판단하고 이 방식으로는 시도하지 않았다.

결국 스스로 풀기에 실패하고 책의 풀이를 참고하였는데, 분할정복으로 푸는 방법은 울타리를 각각 절반으로 푸는 방법이 맞았다. 재귀 함수에서 분할된 두 부분에서 최대 넓이가 나오지 않고 걸쳐있는 부분에서 최대 넓이가 나오는 경우까지 고려하여 최댓값을 계산하도록 풀이하는 방법이었는데, 결국 단순히 문제를 분할하는 것만 생각하는 것이 아니라, 분할된 방법에서 최적화된 답이 나오지 않는 경우, 해당 경우까지 고려하여 비교하였을 때 최적화된 답을 찾는것이 해답이었다.

static int maxArea(int left, int right) {
		//System.out.println("left : "+left+", right : "+right);
		if (left == right)
			return A[left];

		int mid = (left + right) / 2;

		int ret = Math.max(maxArea(left, mid), maxArea(mid + 1, right));

		int low = mid;
		int high = mid + 1;

		int height = Math.min(A[low], A[high]);

		ret = Math.max(ret, height * 2);

		while (left < low || high < right) {
			if (high < right && (low == left || A[low - 1] < A[high + 1])) {
				++high;
				height = Math.min(height, A[high]);
			} else {
				--low;
				height = Math.min(height, A[low]);
			}

			ret = Math.max(ret, height * (high - low + 1));
		}

		return ret;

	}

울타리의 각 높이가 저장된 배열은 전역변수 A로 설정하고, 재귀함수의 매개변수로는 배열의 시작 요소, 끝요소인 left와 right를 갖도록 하여 해당 범위 내에서 최대 사각형의 넓이를 반환하도록 한다. 기저사례는 성분이 하나밖에 없는 경우, 즉 left와 right가 같을 경우 해당 배열 성분값을 반환하도록 한다.

이 때의 범위에서 중간값 mid를 계산하여 절반으로 나누어 재귀함수를 호출하여 분할정복으로 각각 최댓값을 계산하고, 두 값을 비교하여 최대값을 저장한다.

그리고 이 때의 최댓값과 경계 부분을 포함하는 경우의 최댓값을 비교하여야 정확한 최대 넓이가 계산되므로, 경계를 걸친 부분을 최댓값을 계산한다.

경계를 걸친 부분의 최대 넓이를 계산하는 방법은, 먼저 절반으로 나뉘는 경계 양 옆의 울타리를 포함하는 사각형에서 시작하여 각각 왼쪽 끝과 오른쪽 끝을 가로로 확장하며 최대 사각형의 넓이를 계산하도록 한다. 즉, 중간점에서 시작하여 왼쪽과 오른쪽 인덱스를 low, high라 하고 이 때의 최대 넓이를 갖는 높이를 height라 할 때, low와 high가 범위의 끝인 left와 right에 도달할 때까지 한칸씩 확장하여 최대 넓이를 가질 수 있는 높이 height를 계산하고, 해당 높이와 부분 범위 left,right를 통해 넓이를 계산하여 최대 넓이를 구한다.

시간복잡도를 계산해 보면, 걸쳐있는 부분을 고려할 때 길이가 2부터 n까지 확장시키면서 비교하므로 O(n)이 되고, 재귀함수를 절반씩 분할하여 호출하므로 O(logn)의 시간복잡도를 가지므로 전체의 시간복잡도는 O(nlogn)을 갖는다.