알고스팟 : 울타리 잘라내기

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

문제읽기

무식하게 풀자

판자의 높이를 배열로 받아서 h[] 로 처리하고 l번 판자부터 r 번 판자까지 잘라내서 사각형을 만든다고 하면 $(l-r+1)\times{min_{i=l}^{r}}h[i]$

분할 정복 알고리즘의 설계

n개의 판자를 절반으로 나눠 두 개의 부분 문제로 바꾸자. 우리가 찾는 최대 직사각형은 다음 3가지 중 하나에 속할 것이다.

• 가장 큰 직사각형은 왼쪽 부분 문제에서만 찾을 수 있다.
• 가장 큰 직사각형은 오른쪽 부분 문제에서만 찾을 수 있다.
• 가장 큰 직사각형은 왼쪽과 오른쪽 부분에 걸쳐있다.

양쪽 부분 문제에 걸친 경우

정답 직사각형이 반드시 부분 문제의 경계에 있는 두 판자를 포함한다는 것을 고려하여 찾아보자.

코드

#include<iostream>
#include<vector>
using namespace std;

vector<int> h;

int solve(int left, int right) {
	if (left == right) return h[left];
	int mid = (left + right) / 2;
	int ret = max(solve(left, mid), solve(mid + 1, right));
	int lo = mid, hi = mid + 1;

	int height = min(h[lo], h[hi]);

	ret = max(ret, height * 2);
	while (left < lo || hi < right) {
		if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
			++hi;
			height = min(height, h[hi]);
		}
		else {
			--lo;
			height = min(height, h[lo]);
		}
		ret = max(ret, height * (hi - lo + 1));
	}
	return ret;

}

int main() {
	int C, N, elem;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> elem;
			h.push_back(elem);
		}
		cout << solve(0, N-1) << endl;
		h.clear();
	}
	return 0;
}

분석

n크기의 배열을 $\frac{n}2$

int height = min(h[lo], h[hi]);
ret = max(ret, height * 2);

이 부분을 잠시 살펴보자. 우리는 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는 과정을 거쳐야 한다. 왼쪽 또는 오른쪽의 가장 min 값을 찾아서 이 값을 ret과 비교하는데 2를 곱한다. 왜일까.

[mid, mid+1]만 포함하는 너비 2인 사각형을 고려하기 위함이다. ret은 사각형의 넓이를 지칭하는 변수이다. 따라서 우리가 찾는 경계선을 포함한 사각형이 아닌 경계선을 기준으로 왼쪽 또는 오른쪽으로 한칸만 간 사각형까지 고려하여 계산한 것이다.

근데 댓글 보니까 2중 for문으로 푸는게 더 빠르다고 나와있다. 재귀 함수를 위한 문제였던걸로 하자.