[백준 BOJ_6549] 히스토그램에서 가장 큰 직사각형 Python 풀이

출처: 백준 온라인 저지

문제

풀이

문제를 분할하기 위해 아래의 그림과 같이 히스토그램을 반으로 나눈 뒤 가장 큰 직사각형이 왼쪽에 있는 경우와 오른쪽에 있는 경우, 그리고 나눈 중간에 걸쳐있는 경우 세가지로 분할해주었습니다.

왼쪽과 오른쪽의 경우 중 큰 값으로 저장해둔 뒤에 중간에 하나씩 걸쳐있는 것부터 높이가 높은 쪽으로 늘려가며 가장 낮은 높이 또한 저장해가며 비교했습니다.

코드

def solve(blocks, left, right):
    if left == right:
        return blocks[left]
    mid = (left+right) // 2
    ret = max(solve(blocks, left, mid), solve(blocks, mid+1, right))
    lo, hi = mid, mid+1
    height = min(blocks[lo], blocks[hi])
    ret = max(ret, height*2)
    while lo > left or hi < right:
        if lo > left and (hi == right or blocks[lo-1] > blocks[hi+1]):
            lo -=1
            height = min(height, blocks[lo])
        else:
            hi +=1
            height = min(height, blocks[hi])
        ret = max(ret, height*(hi-lo+1))
    return ret
result = []
while(1):
    blocks = list(map(int, input().split()))
    N = blocks[0]
    blocks = blocks[1:]
    if N == 0:
        break
    result.append(solve(blocks, 0, len(blocks)-1))
print(*result, sep="\n")