알고스팟 : 울타리 잘라내기 (분할정복)

 

처음부터 모두 조회하면서 사각형 넓이를 계산하는 완전탐색 실행시 시간초과가 발생하는 문제이다. 이 부분을 해결하기 위해서는 왼쪽과 오른쪽 부분을 나눠서 진행하는데 (분할 정렬처럼) 왼쪽부분에서 가장 큰 사각형과 오른쪽부분에서 가장 큰 사각형 넓이, 가운데에서 가운데 두개의 영역(넓이2 * 둘중에 낮은 높이), 가운데영역을 포함하여 양쪽으로 넓어지면서 계산한 사각형 중에 가장 큰 사각형을 비교하여 가장 큰 넓이를 반환해주여야 한다. 

 

c = int(input())

def max_sqare(left, right, fence):
    # 기저 사레 : 같은 값이면 가로 1 * 높이가 최대 직사각형 
    if left == right : 
        return fence[left]

    # 가운데를 중심으로 나아간다
    mid = (left + right)//2

    # 기준점 양쪽 각각 직사각형 최댓값 중에 최댓값 선택 (가운데 걸치지 않는 경우의 수)
    result = max(max_sqare(left, mid, fence), max_sqare(mid+1, right, fence))

    # 가운데를 걸치면서 넓이가 2일때의 경우의 수 
    l = mid
    r = mid + 1
    h = min(fence[l], fence[r])
    result = max(result, h * 2)

    # 가운데를 걸치는 사각형 경우의 수 (각각 양쪽끝 중에 높이가 높은 곳으로 뻗어나간다)
    while left<l or r<right :
        if r<right and (l == left or fence[l-1]<fence[r+1]):
            r += 1
            h = min(h, fence[r])
        else : 
            l -= 1
            h = min(h, fence[l])
        result = max(result, (r-l+1)*h)

    return result
 

for case in range(c) :
    n = input() 
    fence = list(map(int, input().split()))
    print(max_sqare(0, len(fence)-1, fence))