울타리 잘라내기(FENCE)

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

분할 정복 문제이다.

책을 참고하였다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int solve(int left, int right, vector<int> &v)
{
    // 기저 사례 : 나무 판자가 1개 밖에 없는 경우
    if (left == right) return v.at(left);
 
    // [left, middle], [middle + 1, right]의 2개의 구간으로 나누어 문제를 분할한다.
    int middle = (left + right) / 2;
 
    // 분할한 문제를 각개격파.
    int result = max(solve(left, middle, v), solve(middle + 1, right, v));
 
    // 부분 문제 3 : 나눈 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다.
    int low = middle;
    int high = middle + 1;
    
    // [middle, middle + 1]만 포함하는 너비 2(밑 변의 길이)인 사각형을 고려한다.
    int height = min(v.at(low), v.at(high));
 
    result = max(result, height * 2);
 
    // 사각형이 입력 전체를 덮을 때 까지, 확장해 나간다.
    while (left < low || high < right)
    {
        // 항상 높이가 더 높은 쪽으로 확장한다.
        // high가 right미만이고, (low가 왼쪽 끝까지 갔거나 왼쪽으로 이동했을 때의 높이보다 더 크다면)
        if (high < right && ( left == low || v.at(low - 1) < v.at(high + 1)))
        {
            ++high;
            
            // max가 아닌 이유는 직사각형의 높이를 맞추기 위해서다.
            // 예를 들어 다음 칸이 높이가 더 낮음에도 불구하고,
            // max를 사용하는 것은 가상의 나무 판자가 더 생기는 것과 같다.
            height = min(height, v.at(high));
        }
        else
        {
            --low;
 
            height = min(height, v.at(low));
        }
 
        result = max(result, height * (high - low + 1));
    }
 
    return result;
}
 
int main(void)
{
    int T = 0, N = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        vector<int> v;
 
        int n = 0;
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &n);
 
            v.push_back(n);
        }
 
        printf("%d\n", solve(0, v.size() - 1, v));
    }
 
    return 0;
}