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

백준 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이 하나 주어진다.

출력

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

---

제출

def p(li):
    n=len(li)
    if n == 1: return li[0]
    m=n//2
    l_h=p(li[:m])
    r_h=p(li[m:])
    l,r,u_w=m-1,m,2
    m_h=min(li[l],li[r])
    m_a=u_w*m_h
    while 0<=l and r+1<=n:
        lh=li[l-1] if l>=1 else 0
        rh=li[r+1] if r<n-1 else 0
        m_h = min(m_h,lh) if lh>rh else min(m_h,rh)
        if lh>rh:
            l-=1
        else:
            r+=1
        u_w+=1
        m_a=max(m_a,u_w*m_h)
    return max(l_h,r_h,m_a)
while True:
    n,*l= list(map(int,input().split()))
    if n==0:
        break
    print(p(l))

예제

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

결과

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

 

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