[Algospot] 알고스팟 울타리 잘라내기 문제풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
/*
<문제> - 시간 3초, 메모리 131072kb
울타리에서 직사각형만큼 잘라낼 건데, 가능한 최대 크기를 구하기(비스듬히 불가능)
 
<입력>
C (testcase, <=50)
N (1~20000) -> O(NlogN) 이하여야 함
N개의 정수(왼쪽부터 각 판자의 높이, 모두 10000이하 음이아닌정수)
 
<출력>
각 테스트케이스당 정수 하나 한줄에 출력
 
<풀이>
분할정복 이용
왼쪽부분과 오른쪽부분으로 나누었을 때, 둘 중 더 큰 값 비교
거기에 중간에 걸친 부분이 답일 수 있으므로, 중간에 걸친 경우의 최댓값과도 비교
*/
int fence[20000];    //울타리
 
int split(int l, int r) {    //l~r까지 중 최대 직사각형 넓이 반환
 
    if (l == r)    return fence[l];    //기저사례
    
    int mid = (l + r) / 2;
    int ret = max(split(l, mid), split(mid + 1, r));    //왼쪽부분, 오른쪽부분 중 최대값 구하기
 
    int left = mid, right = mid + 1;    //중간에서 확장
    int height = min(fence[left], fence[right]);
    int width = right - left + 1;
    int maxSize = width * height;
    
    while(true) {
        if (left == l && right == r) break;
        width++;    //너비 1 증가
        if (left - 1 >= l && right + 1 <= r) {    //둘 다 갈 곳이 남아있는 경우
            int tmp = max(fence[left - 1], fence[right + 1]);
            height = min(height, tmp);
            maxSize = max(maxSize, width * height);    //확장 후 넓이 업데이트
            
            if (tmp == fence[left - 1]) left--;    //왼쪽으로 늘린 후
            else right++;
        
        }
        else if (left - 1 < l) {    //왼쪽은 못가는 경우 -> 오른쪽으로 확장        
            height = min(height, fence[right + 1]);
            maxSize = max(maxSize, width * height);    //확장 후 넓이 업데이트
            right++;
        }
        else if (right + 1 > r) {    //오른쪽 못가는경우 -> 왼쪽으로 확장
            height = min(height, fence[left - 1]);
            maxSize = max(maxSize, width * height);    //확장 후 넓이 업데이트
            left--;
        }
 
    }
    return max(ret, maxSize);
}
 
int main() {
    /*
    상자를 반으로 쪼개가며 왼쪽에서만 구한것이 답일경우, 오른쪽에서 구한 것이 답일경우 비교
    */
    int C; cin >> C;
    while (C--) {    //testcase
        int N; cin >> N;
        for (int i = 0; i < N; i++) {
            int f; cin >> f;
            fence[i] = f;
        }
        cout << split(0, N - 1) << endl;
    }
    return 0;
}