[백준]6549 히스토그램에서 가장 큰 직사각형 #세그먼트트리

1. 풀이

이 문제에선 "붙어있는 수열에서 최솟값을 찾는 행위" 를 엄청 많이 해야 한다. (= 이를 쿼리라고 한다)

이때 "붙어있는 수열에서 최솟값을 찾는 행위"를 빠르게 하기 위해 세그먼트트리를 사용한다.

이 문제는 너비는 모든 직사각형이 같지만, 높이만 다르기 때문에 연속된 높이들 중 가장 작은 높이가 만들수있는 직사각형의 높이가 된다. 따라서 높이의 최솟값을 세그먼트 트리에 저장한다.

이때 주의할점은 분할 정복을 할 때 최소 높이를 기준으로 좌 우로 계속해서 탐색을 해야 하기 때문에, 최소높이의 인덱스를 알아야 한다는 것이다. 따라서 세그먼트 트리에는 최소높이와 함께 최소 높이의 인덱스도 저장해야 한다.

 

2. 소스코드

import math
import sys

sys.setrecursionlimit(10**6)

def init(node,start,end):
    if start==end:
        tree[node]=L[start],start
        return tree[node]

    mid=(start+end)//2
    tree[node]=min(init(node*2,start,mid),init(node*2+1,mid+1,end))
    return tree[node]

# 리턴 : [최솟값, 인덱스]
def find(node,start,end,left,right):
    if left<=start and end<=right:
        return tree[node]
    elif end<left or right<start:
        return 1000000001,0
    else:
        mid=(start+end)//2
        return min(find(node*2,start,mid,left,right),find(node*2+1,mid+1,end,left,right))

def dfs(s,e):
    if e<s:
        return 0

    minH,indx=find(1,1,N,s,e)
    now=(e-s+1)*minH

    return max(now,dfs(s,indx-1),dfs(indx+1,e))



while(1):
    L=list(map(int,sys.stdin.readline().rstrip().split()))
    if L[0]==0:
        break
    else:
        N=L[0]
        L[0]=0

        size=2**(math.ceil(math.log(N,2))+1)
        tree=[0 for i in range(size)]
        init(1,1,N)
        print(dfs(1,N))