BOJ 6549 - 히스토그램에서 가장 큰 직사각형

문제 링크(Link)

---

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

문제 해결 (Solution)

---

 1. 여러가지 풀이 방법이 있지만, 분할 정복(divide & conquer)과 구간 트리(segment tree)를 이용해서 문제를 해결.

 2. 가장 큰 직사각형은 일정한 구간 내에서 가장 낮은 높이에 의해 결정된다. 

 3. tree[node] = 일정한 구간 (i, j)에서의 가장 낮은 높이의 인덱스.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 2로 나누고 곱하는 과정을 쉬프트 연산을 이용하면 조금 더 빠르게 해결할 수 있다.

참고(Reference)

---

 -

※ 정확하고 부드러운 태클은 언제나 환영입니다.