https://www.acmicpc.net/problem/4949
- 평이한 Stack 문제이다. 비슷한 문제가 매우 많음.
- 괄호 문제를 Stack 문제로 볼 수 있는 이유는 한번 괄호가 닫히면 그 그 안쪽은 더 이상 볼 필요가 없기 때문이다.
- 유명한 스택 문제들 정리 한번 해보기
- 히스토그램(울타리자르기): 지금 push 할 것보다 큰 울타리는 사각형형이 더 커질 가능성이 없으므로 더 보지 않아도 된다.
- 최대사각형: 히스토그램의 확장버전
- 수족관, BOJ수족관: 한번 높이가 높아지고 나면 그보다 작은거는 볼 필요 없음, 거꾸로된 히스토그램 버전의 문제.
- DFS 중 call-stack이 터지는 류의 문제