링크 : https://algospot.com/judge/problem/read/FENCE
판자의 높이를 배열로 받아서 h[]
로 처리하고 l
번 판자부터 r
번 판자까지 잘라내서 사각형을 만든다고 하면 의 식을 얻어낼 수 있다.
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크기의 배열을 크기의 배열 2개로 나눈 뒤 각각 해결하는 과정이다. 재귀 호출 함수 외에 함수 내에서 하는 일은 두 부분에 걸쳐 있는 사각형을 찾는 일인데 이 작업의 시간 복잡도가 곧 전체 시간 복잡도를 결정한다. 분할 정복 알고리즘은 병합 정렬과 같은 시간 복잡도인 을 갖는다.
int height = min(h[lo], h[hi]);
ret = max(ret, height * 2);
이 부분을 잠시 살펴보자. 우리는 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는 과정을 거쳐야 한다. 왼쪽 또는 오른쪽의 가장 min 값을 찾아서 이 값을 ret과 비교하는데 2를 곱한다. 왜일까.
[mid, mid+1]만 포함하는 너비 2인 사각형을 고려하기 위함이다. ret은 사각형의 넓이를 지칭하는 변수이다. 따라서 우리가 찾는 경계선을 포함한 사각형이 아닌 경계선을 기준으로 왼쪽 또는 오른쪽으로 한칸만 간 사각형까지 고려하여 계산한 것이다.
근데 댓글 보니까 2중 for문으로 푸는게 더 빠르다고 나와있다. 재귀 함수를 위한 문제였던걸로 하자.