백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/6549

아이디어

• 시작점 * 끝점 모든 경우의 수 구할 떄
  • O(N^2) = 1e10 시간초과
• 분할정복을 사용
  • 최소값의 양쪽의 사각형의 넓이 중 큰값을 선택
• 세그먼트 트리로 구현
  • 세그먼트 트리 구성 : 각 노드는 가장 작은값을 가지는 인덱스를 지정
  • 구간에서 가장 작은 값의 인덱스를 찾아서
  • 그 양쪽의 값을 계산해줌

시간복잡도 계산

• 세그먼트 트리 생성 : O(NlgN)
• 검색 및 최대값 계산 : O(lgN)
• 총합 : O(NlgN)

인트 계산

• 세그먼트 값 : 최소 인덱스 : 최대 1e5, INT 가능
• 각 히스토그램 크기 : 최대 1e9, INT 가능
• 사각형 계산 : 최대 1e9 * 1e5 : INT 초과

코드

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int nums[100010];
vector<int> tree;
int N;
 
int make(int node, int st, int en) {
    if(st==en) return tree[node] = st;
    
    int mid = (st+en)/2;
    int li = make(node*2, st, mid);
    int ri = make(node*2+1, mid+1, en);
    
    // 값 비교후 작은 인덱스 표시
    if( nums[li] <= nums[ri]) return tree[node] = li;
    else return tree[node] = ri;
}
 
int find(int node, int st, int en, int li, int ri) {
    if(ri < st || en < li) return -1;
    if(li <= st && en <=ri) return tree[node];
    
    int mid = (st+en)/2;
    int leftIndex = find(node*2, st, mid, li, ri);
    int rightIndex = find(node*2+1, mid+1, en, li, ri);
    
    if(leftIndex == -1) return rightIndex;
    else if(rightIndex == -1) return leftIndex;
    
    
    if(nums[leftIndex] <= nums[rightIndex]) return leftIndex;
    else return rightIndex;
    
}
 
ll query(int st, int en) {
    if(st > en) return 0;
    
    // 최소값을 기준으로 전체, 좌측, 우측 더 작은 값
    // 전체
    int mi = find(1,0,N-1, st, en);
    ll rs = (ll)(en-st+1) * nums[mi];
    rs = max(rs, query(st, mi-1));
    rs = max(rs, query(mi+1, en));
    return rs;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1) {
        fill(nums, nums+100010, 0);
        
        cin >> N;
        if(N==0) break;
        
        tree.clear();
        int h = ceil(log2(N));
        tree.resize(1<<(h+1));
        
        for(int i=0; i<N; i++) cin >> nums[i];
        // 세그먼트 트리 생성
        make(1,0,N-1);
        
        cout << query(0,N-1) << '\n';
        
    }
    
    
    return 0;
}
 

문제유형

• 세그먼트 - 연속된 넓이
  • 트리에 규칙에 맞는 인덱스를 넣고
  • 쿼리를 통해 시작점부터 끝점까지 값을 비교