Treejin's Note

문제 설명

• 너비가 1인 N개의 나무 판자로 이루어진 울타리가 있다. (1 <= N <= 20,000)
• 판자의 높이가 음이 아닌 정수로 주어진다.(0 <= 높이 <= 10,000)
• 해당 울타리를 넓이가 가장 넓은 직사각형으로 잘라내려고 한다.

=> 잘라낼 수 있는 가장 큰 직사각형의 넓이를 출력하기

문제 풀이

울타리를 잘라내는 직사각형을 구할 수 있는 경우의 수는 3가지로 추릴 수 있다.

1. 왼쪽 영역에서 구할 수 있는 가장 큰 직사각형 구하기

2. 오른쪽 영역에서 구할 수 있는 가장 큰 직사각형 구하기

3. 왼쪽과 오른쪽 영역을 걸치는 장 큰 직사각형 구하기

1번, 2번은 재귀를 통해 영역을 이분할 하여

분할된 영역의 왼쪽에서 시작하는 직사각형, 오른쪽에서 시작하는 직사각형을 구한다.

3번의 경우에는 왼쪽과 오른쪽 영역의 가운데에서부터 왼쪽과 오른쪽을 비교해 높이가 높은 쪽을 선택하면서 직사각형의 크기를 구한다.

1번, 2번은 분할 정복을 하므로 O(log n), 3번은 너비가 2인 사각형부터 너비가 n인 사각형까지 탐색하므로 O(n)

따라서 시간복잡도는 O(n log n)이다.

문제 풀이 코드

#include <iostream>
#include <string.h>

using namespace std;

int C, N, maxSize;
int fenceHeights[20000];

int findSquare(int leftIndex, int rightIndex) {
	if (leftIndex == rightIndex) return fenceHeights[leftIndex];	// 너비가 1인 경우
	int mid = (leftIndex + rightIndex) / 2;

	int leftSideMax = findSquare(leftIndex, mid);					// 왼쪽 영역
	int rightSideMax = findSquare(mid + 1, rightIndex);				// 오른쪽 영역

	if (leftSideMax > maxSize) maxSize = leftSideMax;
	if (rightSideMax > maxSize) maxSize = rightSideMax;


	// 가운데 걸치는 경우
	int minMidHeight = fenceHeights[mid] < fenceHeights[mid + 1] ? fenceHeights[mid] : fenceHeights[mid + 1];	
	int centerSideMax = minMidHeight * 2;
	int leftDir = mid;
	int rightDir = mid + 1;
	while (leftDir > leftIndex || rightDir < rightIndex) {
    	// 왼쪽으로 더 나아갈 수 있으면서, 왼쪽이 더 크던가, 오른쪽에 다다랐으면
		if (leftDir > leftIndex && (fenceHeights[leftDir - 1] >= fenceHeights[rightDir + 1] || (rightDir == rightIndex))) {
			--leftDir;
			minMidHeight = fenceHeights[leftDir] < minMidHeight ? fenceHeights[leftDir] : minMidHeight;
		}
		else {
			++rightDir;
			minMidHeight = fenceHeights[rightDir] < minMidHeight ? fenceHeights[rightDir] : minMidHeight;
		}
		int size = minMidHeight * (rightDir - leftDir + 1);
		centerSideMax = size < centerSideMax ? centerSideMax : size;
	}

	if (centerSideMax > maxSize) maxSize = centerSideMax;
}

int main() {
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		cin >> N;
		maxSize = 0;
		for (int i = 0; i < N; ++i) {
			cin >> fenceHeights[i];
		}
		findSquare(0, N-1);

		cout << maxSize << endl;
	}
	return 0;
}