devbelly

문제 https://www.acmicpc.net/problem/6549 알고리즘 스택 풀이 문제 이름에 이미 문제 내용이 적혀 있습니다. 이와 동일한 문제를 이미 분할정복으로 풀이 한 바 있습니다. 여러 가지 풀이가 가능하므로 이번에는 스택으로 풀어보도록 합시다. 문제에서 주어지는 직사각형 $N$개에 대해 다음과 같은 사각형을 정의하겠습니다. $i$번째 직사각형을 최대 높이로 하고 가장 넓은 사각형을 최대 사각형이라고 합시다. 이 최대 사각형이란 녀석은 다음과 같은 특징을 갖고 있습니다. 이 사각형의 가장 왼쪽과 오른쪽은 $i$번째 직사각형보다 낮은 사각형들로 막혀있습니다. 즉 $i$번째 최대사각형을 막는 제일 왼쪽과 오른쪽을 left [i]와 right [i]라고 할 때, 이들을 구하기 위해선 사각형 ..