[C++]algospot FENCE

문제 링크 : https://www.algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

문제

너비가 같은 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

 

문제 풀이

• 분할 정복
• 울타리를 반으로 나누었을 때 직사각형의 최대 넓이를 구할 수 있는 3가지 경우의 수
  ▶ 반으로 나눈 오른쪽 부분에서만 직사각형이 있음
  ▶ 반으로 나눈 왼쪽 부분에서만 직사각형이 있음
  ▶ 반으로 나눈 부분에 직사각형이 걸쳐있음
• 재귀 함수 호출을 통해 위의 3가지 경우의 수를 모두 검증해 가장 큰 넓이를 반환함
• 직사각형이 중간에 걸쳐있는 경우, 중간에서부터 시작해서 오른쪽/왼쪽으로 넓혀가면서 구할 수 있는 가장 큰 넓이를 구함

내가 헤맸던 부분

1. 답이 될 수 있는 경우의 수를 전부 생각 못함
2. 시간초과 : 직사각형이 중간에 걸쳐있을 때, 구간 내 모든 경우의 수를 해 볼 필요 없이 중심에서 시작해서 넓혀가는 방법을 사용하면 시간을 줄일 수 있음

풀이 코드

// 분할 정복
// 140ms
#include <iostream>
#include <math.h>
using namespace std;
int C, N;
int fence[20001];

// ver1. 시간초과
int fenceMax_timeout(int s, int e) {
	// basecase
	if (s == e) return fence[s];

	int mid = (e + s) / 2;
	int res = max(fenceMax_timeout(s, mid), fenceMax_timeout(mid + 1, e));
	
	int smaller = min(fence[mid], fence[mid + 1]);
	for (int height = 1; height <= smaller; height++) {
		int sum = 0;
		for (int cur = mid; cur >= s; cur--) {
			if (fence[cur] >= height) sum += height;
			else break;
		}	
		for (int cur = mid + 1; cur <= e; cur++) {
			if (fence[cur] >= height) sum += height;
			else break;
		}		
		if (sum > res) res = sum;
	}
	return res;
}
// ver2.
int fenceMax(int s, int e) {
	// basecase
	if (s == e) return fence[s];

	int mid = (e + s) / 2;
	int res = max(fenceMax(s, mid), fenceMax(mid + 1, e));

	int H = min(fence[mid], fence[mid + 1]);
	int L = mid, R = mid + 1;
	res = max(res, H * (R - L + 1));
	while (s < L && e > R) {
		if (fence[L - 1] < fence[R + 1]) {
			H = min(H, fence[R + 1]);
			R++;
		}
		else {
			H = min(H, fence[L - 1]);
			L--;
		}
		res = max(res, H * (R - L + 1));
	}
	while (s < L) {
		H = min(H, fence[L - 1]);
		L--;
		res = max(res, H * (R - L + 1));
	}
	while (e > R) {
		H = min(H, fence[R + 1]);
		R++;
		res = max(res, H * (R - L + 1));
	}
	return res;
}

int main() {
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) cin >> fence[j];
		cout << fenceMax(0, N - 1) << endl;
	}
}