|
n = int(input())
l = list(map(int, input().split()))
l.append(0)
l.append(0)
for i in range(n) :
l[n-i] = l[n-i-1]
l[0] = 0
stack = [[0, 0]]
maxarea = 0
for i in range(1, n+2) :
h = l[i]
while stack[-1][1] > h :
sh = stack[-1][1]
del stack[-1]
while stack[-1][1] == sh :
del stack[-1]
area = (i - stack[-1][0] - 1) * sh
maxarea = max(maxarea, area)
stack.append([i, h])
print(maxarea)
|
x축이 날짜, y축이 임금인 좌표평면을 만들면, 매일 급여가 다른 특이한 임금체계(...)때문에 히스토그램이 그려진다.
그리고 연속으로 출근한 일자 중 가장 낮은 임금(y)을 출근일수(x)에 곱하여 한번에 지불하기 때문에
받는 급여는 히스토그램에서 가장 큰 직사각형이다.
아무튼 6549 히스토그램에서 가장 큰 직사각형의 코드(https://uneducatedjungler.tistory.com/34)를 그대로 쓰면 된다는 뜻이다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 1517 버블 소트 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 2749 피보나치 수 3 (0) | 2021.11.17 |
| 파이썬 백준 2696 중앙값 구하기 (0) | 2021.11.17 |
| 파이썬 백준 11286 절댓값 힙 (0) | 2021.11.17 |
| 파이썬 백준 1927 최소 힙 (0) | 2021.11.17 |