BOJ 1725번: 히스토그램

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

이분탐색으로 푸는 방법도 있던데 그 방법은 풀이를 봐도 잘 이해가 되질 않아서 일단 스택으로 풀었다. 더 공부를 해야 할 것 같다.

스택에 0을 미리 넣어놓고, width를 계산할 때 스택에서 pop을 한 후에 i - st[-1] -1 로 계산하는 부분, 그리고 마지막에 인덱스 하나를 더 탐색하는 것이 많이 헷갈렸다..

 

import sys
input = sys.stdin.readline

N = int(input())
arr = [0]*(N+2)
for i in range(1,N+1):
    arr[i] = int(input())

st = [0]
ans = 0

for i in range(1, N+2):
    while (st and arr[st[-1]] > arr[i]):
        height = arr[st[-1]]
        st.pop()
        width = i - st[-1] -1 
        ans = max(ans, height * width)
    st.append(i)
    
print(ans)

알고리즘 하나를 풀면 하루가 다 가는 경우가 많으니,,, 이거 풀다가 오늘 스터디 인증을 까먹었다,,, 슬프다,, 한 번도 놓친 적 없었는데,,,😥