|
import sys
input = sys.stdin.readline
l = ''
while l != [0] :
l = list(map(int, input().split()))
if l != [0] :
n = l[0]
l[0] = 0
l.append(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)
|
입력받은 히스토그램의 양 끝에 높이0의 바닥을 추가하고 스택에 초기값을 넣는다.
i번째의 높이가 stack[-1]보다 작다면, 더이상 stack[-1]의 높이를 세로로 갖는 직사각형은 만들 수 없다.
쓸모없어진 스택들을 날린 뒤 가능한 최대넓이를 체크하여 그것이 기록된 max보다 크다면 갱신
이를 처음부터 끝까지 반복한 뒤 max를 출력한다.
중 난이도의 분할정복 문제라 어제 하루종일 풀이를 생각해봤는데도 안돼서 결국 패스했는데
스택을 쓰니 프리패스다ㅋㅋ
안풀리는 문제를 무한히 붙잡는 인간DFS를 지양하고 때로는 적절한 손절이 필요하다는 교훈
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 18258 큐2 (0) | 2021.11.15 |
|---|---|
| 파이썬 백준 2812 크게 만들기 (0) | 2021.11.15 |
| 파이썬 백준 10000 원 영역 (0) | 2021.11.13 |
| 파이썬 백준 2493 탑 (0) | 2021.11.13 |
| 파이썬 백준 17608 막대기 (0) | 2021.11.13 |