[C++] 6549번 히스토그램에서 가장 큰 직사각형 - 자료 구조, 세그먼트 트리, 분할 정복, 스택

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
const int MAX_N = 100001;
const int MAX_TR = 400001;
const int INF = 1000000001;

using namespace std;
typedef long long ll;

int N;
ll hei[MAX_N], tr[MAX_TR];  //높이와 세그먼트 트리

void input()
{
    memset(hei, 0, sizeof hei);  //초기화
    memset(tr, 0, sizeof tr);
    
    cin >> N;
    FOR(i, 1, N) cin >> hei[i];
}

ll init(ll s, ll e, ll no)
{
    if(s==e) return tr[no]=s;  //단말 노드는 자기 자신
    ll m = (s+e)/2;
    int lid = init(s, m, no*2), rid = init(m+1, e, no*2+1);
    
    return tr[no] = hei[lid]>hei[rid] ? rid:lid;  //둘로 나누기
}

int sum(ll s, ll e, ll no, ll l, ll r)
{
    if(l>e || r<s) return INF;
    if(l<=s && e<=r) return tr[no];
    
    ll m = (s+e)/2;
    int lid = sum(s, m, no*2, l, r);
    int rid = sum(m+1, e, no*2+1, l, r);
    
    if(lid==INF) return rid;
    if(rid==INF) return lid;
    return hei[lid]>hei[rid] ? rid:lid;
}

ll DAQ(int s, int e)
{
    if(s==e) return hei[s];
    
    int m = sum(1, N, 1, s, e);
    ll a, b; a=b=0;
    if(m-1>=s) a = DAQ(s, m-1);
    if(m+1<=e) b = DAQ(m+1, e);
    return max({a, b, (e-s+1)*hei[m]});
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    while(1) {
        input(); if(!N) break;  //0이 입력되면 끝
        ll Max=tr[1]*N;
        
        init(1, N, 1);  //세그먼트 트리 만들기
        cout << DAQ(1, N) << '\n';
    }
    
    return 0;
}

알고리즘은 잘 설명해놓은 글이 백준에 올라와있어서 링크를 참조하면 볼 수 있다. 세그먼트 트리 공부하다가 알게 된 사실인데 펜윅 트리라는 것도 있다고 한다. 아래에 링크를 해놓았다. 세그먼트 트리보다 적은 메모리를 사용해서 풀 수 있다고 하니 메모리 부족할 때 용이하게 쓸 수 있을 것 같다.

 

 

 

 

 

<Fanwick Tree 1>

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

 

<Fanwick Tree 2>

https://yabmoons.tistory.com/438

[ 펜윅트리(FenwickTree) ] 개념과 구현방법 (C++)

 

<문제 알고리즘>

https://www.acmicpc.net/blog/view/12

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

 

 

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.