[BOJ 6549, Python 3] 히스토그램에서 가장 큰 정사각형

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

 

풀이

이 문제는 다양한 풀이가 있는데 저는 세그먼트 트리를 이용한 분할 정복 풀이를 사용하였습니다.

먼저 arr[0] ~ arr[n-1]의 모든 구간을 잡은 뒤, 세그먼트 트리를 이용하여 가장 낮은 높이의 최솟값을 찾습니다.

그래서 (구간 길이) * (제일 작은 높이)를 구하여 답을 갱신시켜준다음, 이 가장 낮은 높이를 가진 인덱스를 기준으로 가장 낮은 높이를 가진 인덱스를 제외하고 오른쪽, 왼쪽으로 구간을 나눠줍니다.

왜 쪼개냐면 이제 높이가 제일 작은 곳을 곱한 구간은 저게 최대이기 때문에 더 이상 볼 필요가 없습니다. 그래서 다음으로 높이가 낮은 구간을 찾아서 넓이를 구하고 답을 갱신하고, ... 이렇게 반복하는 것 입니다.

 

세그먼트 트리는 가장 낮은 인덱스를 구할 수 있도록 만들어주면 됩니다.

 

 

코드

def update(now, s, e):
    if s == e:
        tree[now] = s
        return tree[now]
    mid = (s + e) // 2
    tree[now] = tree[now*2] if arr[update(now * 2, s, mid)] <= arr[update(now * 2 + 1, mid+1, e)] else tree[now*2+1]
    return tree[now]
 
def find_min(now, s, e, L, R):
    if s > R or e < L: return -1
    if L <= s and e <= R: return tree[now]
    mid = (s + e) // 2
    x = find_min(now * 2, s, mid, L, R)
    y = find_min(now * 2 + 1, mid + 1, e, L, R)
    if x == -1: return y
    if y == -1: return x
    return x if arr[x] <= arr[y] else y
 
def go(l, r):
    global res
    idx = find_min(1, 0, n-1, l, r)
    res = max(res, (r - l + 1) * arr[idx])
    if l < idx: go(l, idx-1)
    if r > idx: go(idx+1, r)
 
import sys
sys.setrecursionlimit(200000)
input = __import__('sys').stdin.readline
while 1:
    arr = [*map(int, input().split())]
    if arr[0] == 0: break
 
    n = arr[0]
    arr = arr[1:]
    tree = [0] * (4 * n)
    update(1, 0, n-1)
 
    res = 0
    go(0, n-1)
    print(res)