[#2-4]분할정복-문제: 울타리 잘라내기(문제 ID: FENCE)

                문제

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<iostream> #include<vector> #include<algorithm> using namespace std; int solve(vector<int> &h, int left, int right) {     //기저사례: 판자를 다 분해한 경우     if (left == right)         return h[left];     //[left,mid],[mid +1, right]의 두 구간으로 문제를 분할한다.     int mid = (left + right) / 2;     //분할한 문제를 다시 재귀함수를 불러서 최대값을 갖는 사각형 구분     int result = max(solve(h, left, mid), solve(h, mid + 1, right));     //맨 밑까지 내려왔다면 지금부터는 사각형 중 가장 큰 것을 골라서 위에 함수에 반환     int low = mid, high = mid + 1;     int height = min(h[low], h[high]);     //[mid, mid+1]만 포함하는 너비 2인 사각형 고려한다.     result = max(result, height * 2);     //사각형이 입력 전체를 덮을 때까지 확장해 나간다.     while (left < low || high < right)     {         if (high < right && (low == left || h[low - 1] < h[high + 1]))         {             high++;             height = min(height, h[high]);         }         else         {             low--;             height = min(height, h[low]);         }         //확장 후 사각형의 넓이         result = max(result, height*(high - low + 1));     }     return result; } int main(int argc, char* argv[]) {     int Testcase;     int num;     cin >> Testcase;          if (Testcase <= 0 || Testcase > 50)         return 0;     for (int i = 0; i < Testcase; i++)     {         cin >> num;         vector<int> h(num, 0);                  for (int j = 0; j < num; j++)             cin >> h[j];         cout << solve(h, 0, h.size() - 1) << endl;     } } Colored by Color Scripter

cs

문제풀이

이 문제는 2중 for문으로 모든 경우의 수를 고려하는 방법도 있지만 최대 입력수가 20000까지 가능하므로 알고리즘 복잡도가 O(n^2)이 되므로 사용이 불가능하다. 그래서 분할정복 방식으로 접근해야 한다.

 

밑에는 문제의 예제인 7 1 5 9 6 7 3을 입력할시 코드의 흐름을 그림으로 분석한것이다.

이해가 안가면 참고해보면 좋을거같다.

재귀호출 순서