백준 1725 (히스토그램) c++

문제

1725번: 히스토그램

n개의 밑변의 길이가 1인 직사각형이 차례대로 주어져 막대그래프를 이루는 것이 히스토그램이라고 합니다.

히스토그램 내에서 가장 큰 직사각형의 넓이를 구하면 됩니다.

예를 들어 n이 7이고 밑변의 길이가 1인 직사각형이 차례대로 {2, 1, 4, 5, 1, 3, 3} 이라면 

다음과 같은 히스토그램이 완성됩니다. 이러한 히스토그램에서 가장 큰 직사각형을 그리면

다음과 같습니다. 따라서 주어진 히스토그램에서 가장 큰 직사각형의 넓이는 8이 됩니다.

 

단순히 차례대로 맨 왼쪽을 기준으로 잡아 사각형을 늘려나가면서 최대의 사각형을 찾는 것은 

시간복잡도가 O(N^2)이 나와 시간초과가 나오게 됩니다.

 

다른 방법으로는 만약 현재 K번째 사각형을 가리킨다면 K번째 사각형을 포함해서 

오른쪽, 왼쪽을 살펴보면서 높이가 더 큰쪽으로 사각형을 넓혀 나가는 방법이 있습니다.

 

하지만 이러한 방법도 결국 오른쪽이나 왼쪽으로 계속해서 나아가므로 O(N)의 시간복잡도를 가져

모든 사각형에 대해서 이러한 방법을 사용하면 O(N^2) 이 됩니다.

 

이러한 방법을 바탕으로 시간복잡도를 줄일려고 생각하면 분할해서 문제를 해결하는 아이디어를 얻을 수 있습니다.

1) 현재 사각형을 포함하는 직사각형중 제일 큰 넓이

2) 현재 사각형을 포함하지 않는 직사각형 (왼쪽, 오른쪽 2가지로 나뉨)

따라서 히스토그램중 제일 큰 사각형의 넓이는

MAX(현재 사각형을 포함하는 직사각형중 제일 큰 넓이, 현재 사각형을 포함하지 않으면서 제일 큰 왼쪽 넓이,

현재 사각형을 포함하지 않으면서 제일 큰 오른쪽 넓이) 입니다.

 

cin >> n;
for (int i = 0; i < n; i++) 
	cin >> v[i];
cout << histogram(0, n - 1);

n을 입력받고 n개의 높이를 v배열에 입력받습니다.

histogram함수를 실행해줍니다.

int histogram(int s, int e) {
    if (s == e)return v[s];
    int mid = (s + e) / 2;
    int ret = v[mid]; 
    int h = v[mid]; 
    int l = mid - 1;
    int r = mid + 1;
    while (s <= l || r <= e) {
        if (s > l) {
            h = min(h, v[r]);
            r++;
        }
        else if (r > e) {
            h = min(h, v[l]);
            l--;
        }
        else if (v[l] > v[r]) {
            h = min(h, v[l]);
            l--;
        }
        else {
            h = min(h, v[r]);
            r++;
        }
        ret = max(ret, (r - l - 1) * h);
    }
    ret = max(ret, max(histogram(s, mid), histogram(mid + 1, e)));
    return ret;
}

histogram의 함수 입니다. 인자로 int s, int e 시작점과 끝점을 받습니다.

2번째 줄을 보면 s와 e가 같으면 결국 직사각형이 한개밖에 없다는 의미이므로 그대로 높이를 return해 줍니다.

변수 ret는 가장 큰 직사각형의 변수가 담길 것입니다. 따라서 처음에는 mid의 높이가 들어갑니다.

변수 h는 현재 직사각형을 포함해서 중간에서 넓어질때 최고 높이입니다. 현재 직사각형은 mid 이므로

mid의 높이가 들어갑니다.

변수 l과 r은 mid에서 직사각형이 넓어질때 왼쪽, 오른쪽 위치를 가리킵니다.

 

이제 8번쨰 줄을보면 본격적으로 현재 직사각형(mid)를 포함해서 가장큰 직사각형의 넓이를 구할 것입니다.

현재 높이(h)보다 더 큰 쪽에만 넓어 질 수 있습니다.

 

9번쨰 줄을 보면 더 이상 왼쪽으로 가지 못하는 경우 입니다. 따라서 오른쪽의 부분을 넓혀 줍니다.

13번째 줄을 보면 더 이상 오른쪽을 가지 못하는 경우 입니다. 따라서 왼쪽의 부분을 넓혀 줍니다.

17번째 줄을 보면 왼쪽의 높이가 더 큰 경우 입니다.

21번째 줄을 보면 오른쪽의 높이가 더 큰 경우 입니다. 

25번째 줄을 보면 이제 왼쪽이나 오른쪽으로 늘어난 밑변(r-l-1)을 통해 현재 높이 (h)와 곱해 

가장 큰 넓이가 ret변수에 들어가게 됩니다.

 

27번째 줄을 보면 이제 분할을 통해 최고 넓에를 ret에 저장해줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
int v[100001];
int histogram(int s, int e);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> v[i];
    
    cout << histogram(0, n - 1);
 
    return 0;
}
int histogram(int s, int e) {
    if (s == e)return v[s];
    int mid = (s + e) / 2;
    int ret = v[mid]; 
    int h = v[mid]; 
    int l = mid - 1;
    int r = mid + 1;
    while (s <= l || r <= e) {
        if (s > l) {
            h = min(h, v[r]);
            r++;
        }
        else if (r > e) {
            h = min(h, v[l]);
            l--;
        }
        else if (v[l] > v[r]) {
            h = min(h, v[l]);
            l--;
        }
        else {
            h = min(h, v[r]);
            r++;
        }
        ret = max(ret, (r - l - 1) * h);
    }
    ret = max(ret, max(histogram(s, mid), histogram(mid + 1, e)));
    return ret;
}