[WEEK02] 백준 6549 히스토그램에서 가장 큰 직사각형

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

풀이

분할정복으로 풀어주었다.
영역의 길이가 1이면 막대기 단일 넓이를 리턴해주었고,
해당 영역에서의 중간 인덱스와 옆의 인덱스 2개를 선택해주어 둘의 높이중 작은거를 선택해 넓이를 구해주고 양쪽으로 넓혀주면서 최대 넓이의를 갱신해준다.

첫 스타트는 mid, mid + 1 막대기 2개로 시작하고, 양쪽으로 넓힐 때
더 높은쪽으로 먼저 확장해주는 식으로 진행했다.

전체코드

import sys

def func(left, right):
    if left == right:
        return arr[left]
    
    mid = (left + right) // 2

    result_l = func(left, mid)
    result_r = func(mid + 1, right)

    i = mid
    j = mid + 1
    w = 2
    h = min(arr[i], arr[j])
    result_m = 2 * h

    while left < i or j < right:

        if j < right and (left == i or arr[i - 1] < arr[j + 1]):
            j += 1
            w += 1
            h = min(h, arr[j])
        else:
            i -= 1
            w += 1
            h = min(h, arr[i])
        result_m = max(result_m, w * h)

    return max(result_l, result_m, result_r)


while True:
    input = list(map(int, sys.stdin.readline().split()))
    n = input[0]
    arr = input[1:]
    if n == 0: sys.exit()

    print(func(0, n - 1))