백준 6549번, 히스토그램에서 가장 큰 직사각형
문제 BOJ 6549번 풀이 히스토그램 문제에 스택과 세그먼트 트리를 사용한 풀이가 있는데, 세그먼트 트리를 사용하여 풀어보겠습니다. 위와 같은 히스토그램이 있습니다. 아래와 같은 분할 정복을 사용하여 문제를 풀어보겠습니다. * 구간 [left, right]를 정복하고 있을 때, - 해당 구간에서 최소 높이를 h라고 두고, 높이가 h인 직사각형의 인덱스를 i라고 하겠습니다. - (right - left + 1) * h가 답이 될 수 있습니다. - 그리고 구간 [left, i - 1]과 [i + 1, right]에서 다시 분할 정복을 해나가면 됩니다. 테스트케이스를 예시로 설명해보겠습니다. [1, 7]을 정복하고 있을 때 2번째 직사각형의 높이가 1로 가장 작으니(최솟값이 여러개 있으면 아무거나 선택해도 ..
2020.10.02