[BOJ/백준] 6549 히스토그램에서 가장 작은 직사각형

import sys

input = sys.stdin.readline


while True:
    N,*arr = list(map(int,input().split()))

    if N == 0:
        break

    stack = [0]
    arr = [0] + arr[:] +[0]
    result = 0
    for ind in range(1,len(arr)):
        while stack and arr[ind] < arr[stack[-1]]:
            height = arr[stack[-1]]
            stack.pop()
            width = ind - stack[-1]-1
            result = max(result,height*width)
        stack.append(ind)

    print(result)

 이 문제는 boj.kr/11873 의 하위호환이다.

 

11873의 문제를 푼것과 같이 stack에 현재위 index 즉 가로길이를 넣어주는 걸 한다.

 

그리고 이걸 좀 더 쉽게 구하기 위해, 양 끝에 [0]을 추가를 해준다.

 

그러면 스택에서 마지막 값에 위치한 높이보다 작은 높이가 들어오면,

 

그때 스택에서 값을 추출해서, 지금까지의 거리를 측정을 해준다.

 

측정 방식은 현재 index에서 stack의 마지막값을 빼준 값에 -1을 해준것이다.

 

이렇게 2개의 값을 곱한뒤 최대값을 저장해주면 된다.