<문제링크>
https://algospot.com/judge/problem/read/FENCE
너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.
판자의 너비는 모두 1이라고 가정합니다.
위의 문제를 푸는 방법은 다양하다. 하지만 그중에서도 분할정복으로 위의 문제는 해결이 가능하다. 우선 전체 판자의 범위가 문제에서 주어질 것이다. 범위가 n이라고 하면 배열 0 ~ n - 1까지의 범위에 각 판자의 높이가 저장될 것이다. 우리는 범위를 반반씩 나눈다.
mid = (시작점 + 끝점) / 2
leftMax = (start, mid)
rightMax = (mid + 1, end)
재귀 함수를 이용하여 분할정복을 실시하면 각 재귀 스택마다 반씩 나누에 호출했던 함수에서 각 각의 범위에 대한 최대 판자의 넓이를 반환할 것이다. 그렇다면 우리는 현재 스택의 최대 판자값을 아래와 세개의 값중에서 선택하면된다.
1.leftMax
2.rightMax
3.왼쪽과 오른쪽의 부분에 걸쳐진 값.
1, 2는 현재스택에서 호출되었던 함수의 반환값으로 얻어진상태 우리는 3을 구하면된다. 3을 구하는 방법은 현재의 모든칸을 순회하면 되는데 다음과 같은 방법으로 구현하면 된다.
(1) 두범위에 걸쳐있는 경우이므로우선 가운데 경계가되는 두칸은 항상 포함 되어야 된다.
(2) 현재 상태에서 한칸씩 왼쪽이나 오른쪽으로 범위를 늘려가면서 판자의 넓이를 계산하고 이중 최댓값이 3의 값이된다.
(3) 왼쪽이냐 오른쪽이냐를 결정할때에는 당연히 높이가 더 높은 판자의 방향을 우선적으로 포함시키고 판자의 넓이를 계산해야된다.
코드는 아래와 같다.
int cutFence(const vector<int> &hight, int start, int end){
//기저사례(base case)
if(start >= end) return hight[end];
int mid = (start + end) / 2;
//절반을 기점으로 왼쪽과 오른쪽 범위의 최대 판자 넓이를 구한다.
int leftMax = cutFence(hight, start, mid), rightMax =
cutFence(hight, mid + 1, end);
//경계가되는 판자두개는 무조건 포함
int h = min(hight[mid], hight[mid + 1]);
//걸쳐있는 판자의 최대치
int merge = 2 * h;
int left = mid - 1, right = mid + 2;
//판자 높이가 더 높은방향으로 범위를 한칸씩 확장하면서
//최대의 merge값을 구한다.
while(left >= start || right <= end){
if(left < start){
h = min(h, hight[right]);
merge = max(merge, h * (right - left));
++right;
}
else if(right > end){
h = min(h, hight[left]);
merge = max(merge, h * (right - left));
--left;
}
else{
if(hight[left] >= hight[right]){
h = min(h, hight[left];
--left;
}
else{
h = min(h, hight[right]);
++right;
}
merge = max(merge, h * (right - left));
}
}
//leftMax, rightMax, merge 중 가장 큰값이 현재범위의 최대 판자 넓이가된다.
int ret = max(leftMax, rightMax);
return ret = max(ret, merge);
}
위의 분할정복 코드는 merge를 구하는데 O(N)의 시간이 리고 최대 재귀 호출의 횟수는 O(lgN)이 된다. 그러므로 전체 시간복잡도는 O(NlgN)이 된다.
(N = 울타리의 길이)