본문 바로가기

카테고리 없음

[백준 12846번] 무서운 아르바이트 (Python3)

N,data = int(input()),[*map(int,input().split())]+[0]
histogram,result = [],0
for i in range(N+1):
  j = i
  while histogram and histogram[-1][0]>=data[i]:
    h,j = histogram.pop()
    result = max(result,h*(i-j))
  histogram.append((data[i],j))
print(result)

히스토그램에서 가장 큰 직사각형 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 문제와 완전히 똑같은 문제이다.

기존의 코드에서 data에 0을 추가하는 방식으로 약간의 코드개선을 하였다.