(6549) 히스토그램에서 가장 큰 직사각형

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

단계별로 풀어보기

24단계(분할 정복) 9번째

 

 

 

단계별 문제에서 처음으로 등장하는 플래티넘 문제다. 그만큼 매우 어렵다.

분할 정복으로 푸는 방법을 간단하게 설명하면

1) 구간 (i,j)에 대해 i=j가 아니라면 가운데를 기준으로 자른다. 맞다면 현재 구간의 높이(=구간에서 직사각형의 최대 넓이)를 리턴한다.

2) 가운데를 기준으로 자른 왼쪽 구간과 오른쪽 구간 각각의 최대값을 재귀를 이용해 구한다.

3) 왼쪽 구간과 오른쪽 구간을 둘 다 포함하는 직사각형이 최대 넓이일 수도 있으므로 이를 구한다.

4) 2번과 3번에서 구한 최댓값을 전부 비교해 가장 큰 값을 리턴한다.

3번에서 구간 전체를 탐색해야 하므로 O(N)이 걸리고, 분할 정복에 O(log N)이 걸리므로

코드의 전체 시간복잡도는 O(N log N)이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

void solve(int n){
  vector<long> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  auto func= [&](auto self, int lo, int hi) -> long {
    if(lo==hi)  return v[lo];
    
    int mid= (lo+hi)/2;
    
    int l= mid, r= mid;
    long h= v[mid], area= v[mid];
    
    while(lo<l && r<hi){
      if(v[l-1]<v[r+1]){
        r++;
        h= min(h, v[r]);
      }else{
        l--;
        h= min(h, v[l]);
      }
      
      area= max(area, h*(r-l+1));
    }
    
    while(lo<l){
      l--;
      h= min(h, v[l]);
      area= max(area, h*(r-l+1));
    }
    
    while(r<hi){
      r++;
      h= min(h, v[r]);
      area= max(area, h*(r-l+1));
    }
    
    return max(area, max(self(self, lo, mid), self(self, mid+1, hi)));
  };
  
  cout << func(func, 0, n-1) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  while(true){
    cin >> n;
    
    if(!n)  break;
    
    solve(n);
  }
  
  return 0;
}