분할 정복. [6549]

[1. 문제 설명]

밑변이 1이고, 높이가 서로 다른 직사각형이 일렬로 인접하여 놓여 있을 때,

가장 넓이가 큰 직사각형을 구해야 함

 

 

[2. 풀이 접근]

1. 완전탐색 풀이

• l: 왼쪽 offset
• r: 오른쪽 offset
• h: [l, h] 에서 최소 높이
• 넓이 = (l - r + 1) * h
• => 모든 l 과 h 에 대해서 넓이의 최소 값을 갱신해나가는 방법
•  
• 이 방법은 n^2 의 시간 복잡도를 갖게 된다.
• 10^10 이므로 제한시간내 풀이가 불가능 함

 

2. 분할정복

하나의 큰 히스토그램을 아래와 같이 분할

1. [Left, Mid]
2. [Mid+1, Right]
3. Mid 를 중심으로 왼쪽과 오른쪽을 겹치도록

1과 2는 탐색 범위를 절반씩 줄여나가므로, logn 의 시간복잡도를 갖고,

3번은 Mid 를 중심으로 해서 왼쪽 끝, 오른쪽 끝으로 이동해나가므로 n 의 시간복잡도를 갖는다.

총 nlogn 의 시간복잡도를 갖는다.

 

 

[3. 코드]