[분할정복] 울타리 잘라내기 (FENCE) 문제

출처 - 알고스팟

 문제를 요약하면 나무판자 내에서 가장 크기가 클 수 있는 직사각형의 크기를 구하는 문제이다.

 이 문제는 모두 찾아보는 브루트포스 방식과 절반으로 나누어서 해결하는 분할 정복 이 두가지 등으로 해결이 가능합니다. 첫 번째 브루트포스는 해보았지만 역시나 시간 복잡도가 O(n²)라서 시간초과가 떴습니다. 그래서 분할정복으로 문제를 해결하였습니다.

 밑의 코드가 해결코드이며 코드 설명은 주석으로 달아 놓았습니다.

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int cur_size; // 각 케이스 마다 입력받는 현재 크기를 나타낸다.

vector<int> fense; // 팬스의 높이를 순서대로 가지고 있는 벡터

//left~right 구간에서 찾을 수 있는 가장 큰 사각형의 넓이를 반환한다.

int solve(int left, int right) {

       if (left == right) // 범위가 1이면 해당 값을 반환 (기저사례)

              return fense[left];

       int mid = (left + right) / 2; // 아닐경우 절반으로 나누어 해결

       int ret = max(solve(left, mid), solve(mid+1, right));

       int lo = mid, hi = mid + 1; // mid 기준 좌우로

       int height = min(fense[lo], fense[hi]);// 너비가 2인 사각형을 계산 하기위해 가장 낮은 높이를 가져온다.

       ret = max(ret, height * 2); // 너비가 2인 사각형을 계산

       while (left < lo || hi < right) { // 높이가 높은 쪽을 우선시하면서 범위 내 사각형을 키워나간다.

              if (hi < right && (lo == left || fense[lo - 1] < fense[hi + 1])) {

                     //hi가 다 증가되지 않았고, lo가 끝이거나 hi쪽이 더 높을 때

                     ++hi;

                     height = min(height, fense[hi]);

              }

              else {

                     --lo;

                     height = min(height, fense[lo]);

              }

              ret = max(ret, height*(hi - lo + 1)); // 넓이를 갱신한다.

       }

       return ret; // 가장 큰 넓이를 반환한다.

}

int main() {

       int c;

       cin >> c;

       for (int i = 0; i < c; ++i) {

              cin >> cur_size;

              vector<int> fense_(cur_size);

              fense = fense_;

              for (int j = 0; j < cur_size; ++j) {

                     cin >> fense[j];

              }

              //solve

              cout << solve(0,cur_size-1) << endl;

       }

       return 0;

}