while True:
temp = list(map(int, input().split()))
n = temp[0]
if n == 0:
break
heights = temp[1:]
heights.insert(0, 0)
heights.append(0)
# 스택에는 인덱스를 저장한다. 현재 인덱스의 높이보다 높은 애들만 남는다.
# 현재 바로 전까지 모든 인덱스 중 그 전보다 높이가 상승한 애들의 인덱스만 남는다.
check = [0]
area = 0
for i in range(1, n+2):
while check and heights[i] < heights[check[-1]]:
# 현재 높이가 전 높이보다 낮으면 낮아진 높이로 넓이를 계산한다.
# 내 전 직사각형 중 나보다 높은 애들
prev_idx = check.pop()
# 스택에서 없애고 현재 인덱스에 저장한다.
# 한 번 높이가 높아졌다 낮아지면 높았던 높이의 넓이는 최대치만 고려하면 되므로
# 그 인덱스들은 이제 고려할 필요가 없기 때문이다.
area_in_prev_idx = (i-1-check[-1])*heights[prev_idx]
# 직전 높이에서의 최대 넓이
area = max(area, area_in_prev_idx)
# 내 전보다 높이가 나보다 낮은 애들은 일단은 고려하지 않는다.
# 뒤에 그 높이보다 낮은 높이가 나오면 그때 계산한다(하물며 맨 마지막으로 가서 0이랑 비교하든가)
check.append(i)
# 지금 인덱스를 스택에 저장한다.
# 뒤에 나올 높이가 지금 높이보다 높다면 쭉 스택에 저장될 것이고
# 낮다면 이 인덱스를 가지고 넓이를 계산할 것이다.
print(area)
import sys
def max_square(left, right):
# 우선 경계선이 1 ~ n 까지인 애들 중 가장 큰 값을 찾고
# 리턴값으로 비교하면서 경계선이 1~(n+1)//2, (n//2)+1~n 까지인 애들의 최대값과 비교하고
# 재귀를 쭉 반복
if left == right: # 너비가 1이라면
return lst[left] # 그 좌표에서의 높이(넓이)를 반환한다.
else: # 너비가 1이 아니라면
# 경계선 왼쪽과 오른쪽, 경계선에 걸쳐 있는 최대 직사각형 중 최댓값을 반환한다.
# 경계선에 걸쳐 있는 직사각형 중 최댓값인 temp를 구한다
mid = (left + right) // 2
pl = mid # 경계선
pr = mid + 1 # 경계선보다 한 칸 오른쪽
min_height = min(lst[pl], lst[pr]) # 그 둘 중 작은 값
temp = min_height * 2 # 오른쪽, 왼쪽 두 블록을 합한 넓이. 얘가 temp이다.
# 왼쪽으로 한 칸, 오른쪽으로 한 칸씩 넓혀가면서 temp를 수정한다.
width = 2
while True:
if (lst[pl] == 0 or pl == left) and (lst[pr] == 0 or pr == right):
break # pl과 pr이 둘 다 양쪽 끝 인덱스인 left, right를 만나거나 높이가 0인 직사각형을 만나면
# 한 쪽이 높이 0을 만나거나 끝까지 가면 다른 한 쪽만 1씩 증가시켜준다.
elif lst[pl] == 0 or pl == left:
if lst[pr + 1] < min_height:
min_height = lst[pr + 1]
pr += 1
elif lst[pr] == 0 or pr == right:
if lst[pl - 1] < min_height:
min_height = lst[pl - 1]
pl -= 1
else: # 둘 다 갈 수 있다면 둘 다 늘려준다.
# 둘 중 큰 높이를 골라, min_height와 비교한다. 그리고 큰 높이를 가진 쪽을 더 늘려준다.
# 최댓값을 구해야 하기 때문
# 큰 높이가 min_h보다 작으면 높이를 그것으로 교환한다.
if lst[pl - 1] > lst[pr + 1]:
if lst[pl - 1] < min_height:
min_height = lst[pl - 1]
pl -= 1
else:
if lst[pr + 1] < min_height:
min_height = lst[pr + 1]
pr += 1
width += 1 #
temp = max(temp, min_height * width)
return(max(max_square(left, mid), max_square(mid + 1, right), temp))
# 경계선 왼쪽(max_square(left, mid))과 오른쪽(max_square(mid + 1, right)),
# 경계선에 걸쳐 있는 최대 직사각형(temp) 중 최댓값을 반환한다.
while True:
lst = list(map(int, sys.stdin.readline().split()))
n = lst[0]
if lst[0] == 0:
break
print(max_square(1, len(lst)-1))
히스토그램을 가로로 자를 수 있는 높이와 히스토그램 리스트를 인자로 받아오는 재귀함수를 만든다.
메모리 초과로 실패하였다.
import sys
sys.setrecursionlimit(1000000)
def recur(h: int, a: list) -> int:
n = len(a)
max_area = 0
area = 0
if h == 0:
return 0
# 각 원소들과의 대소 비교를 통해서 영역을 구한다.
for i in range(n):
if a[i] >= h: # 해당 원소가 기준보다 크다면
area += h # 넓이를 누적한다.
if area >= max_area:
max_area = area
else: # 해당 원소가 기준보다 작다면
area = 0
before_area = recur(h-1, a)
if max_area > before_area:
return max_area
else:
return before_area
lst_list = []
while True:
lst = list(map(int,input().split()))
if lst[0] == 0:
break
lst_list.append(lst)
for lst in lst_list:
print(recur(max(lst), lst[1:]))