BOJ - (Algospot) FENCE 해결 전략 (C++)

• 문제

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

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

• 입력

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

• 출력

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

• 예제 입력
  3
  7
  7 1 5 9 6 7 3
  7
  1 4 4 4 4 1 1
  4
  1 8 2 2

• 예제 출력
  20
  16
  8

해결 전략

  본 문제는 Naive한 Brute-Force 알고리즘이 곧바로 떠오르는, 문제 상황 이해가 어렵지 않은 문제이다. 관건은 문제의 입력이 크다는 것으로, 중첩 반복문으로 구성되는 브루트포스 알고리즘은 본 문제의 N이 최대 20000이라는 점에 의해 폐기해야한다. 최소 O(N^2)의 복잡도를 가지기 때문이다.

  폐기 후, 이어서 Divide & Conquer 접근이 자연스럽게 떠오르는 문제이다. 본인은 최초 문제 풀이 시 이 부분에서 '반으로 나누지 않는 실수'를 저질러 결국 최종적으로 해결하지 못하였다.

  여기서의 가장 주요한 포인트는, 문제 입력을 반으로 나누고, 좌/우측은 재귀 호출에 의해 알아서 풀리게 만들고, 중간, 즉, 좌/우에 각각 걸치는 직사각형의 넓이를 고려해, 좌에서의 직사각형, 우에서의 직사각형, 중간에서의 직사각형 중 최대인 친구를 업데이트하는 방식으로 해결해야한다는 점이다.

  본인은, 반으로 분할하는 것을 생각하지 않고, 배열에서 최소값을 도출해서 나누는 방식으로 해결하려 하다보니 끝 마무리를 계속 실패했다. 테스트 케이스의 절반만 해결이 가능한 반쪽짜리 알고리즘을 만들었던 것이다.
  학부 알고리즘 수업에서 다루었던 Minimum Distance 문제의 해결 전략과 매우 유사한 접근법이 필요했던 문제로, "반으로 나누고 중간 부분을 처리한다."는 Idea가 주요하다. 이를 반드시 체화시키자.

  한편, 중간 부분 계산에서 도입되는, 양쪽으로의 확장 기법에서 high와 low, left, right를 이용한 선형적 확장 방식은 주목할만하다. 병합 정렬의 Idea가 변형된 형태인데, 이때, fence[low]와 fence[high] 중 더 큰 것을 택하면서 확장해야 올바르게 직사각형 넓이를 고려할 수 있음을 알아내는 것이 획기적이다. 이에 대한 Proof of Optimality는 교재에 명시되어 있다. 아래는 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
// Algospot - FENCE
using namespace std;

int solve(vector<int> &fence, int left, int right) {
	if (left == right) // Base : 막대가 하나밖에 없는 경우
		return fence[left];

	int mid = (left + right) / 2; // [left, mid], [mid+1, right] 두 구간으로 분할
	int result = max(solve(fence, left, mid), solve(fence, mid + 1, right));
	//부분 문제 3:두 부분에 모두 걸치는 사각형 중 가장 큰 것
	int low = mid, high = mid + 1;
	int height = min(fence[low], fence[high]);

	result = max(result, height * 2); // [mid, mid+1]의 너비 2인 직사각형

	while (left < low || high < right) { // 직사각형을 양쪽 방향으로 확장
		if (high < right && (low == left || fence[low - 1] < fence[high + 1])) {
			high++;
			height = min(height, fence[high]);
		} // 높이가 더 높은쪽으로 확장한다. 그래야 기존 height와 비교했을때 올바른
		else { // 결과를 도출할 수 있으므로
			low--;
			height = min(height, fence[low]);
		}
		result = max(result, height*(high - low + 1)); // 확장 결과를 업데이트
	}

	return result;
}

int main(void) {
	int C, num;

	cin >> C;
	while (C--) {
		cin >> num;

		vector<int> fence(num, 0);

		for (int i = 0; i < num; i++)
			cin >> fence[i];

		cout << solve(fence, 0, fence.size() - 1) << "\n";
	}

	return 0;
}