글 읽기 - 세그먼트 트리를 사용한 분할 정복] 메모리 초과가 납니다

ryute 5년 전 0

분할정복 기반으로 왼쪽/오른쪽 히스토그램과 양쪽 히스토그램 중 최댓값을 찾는 방식으로 메소드를 구현하고
그 과정에서 RMQ를 사용해서 최소 높이를 찾았는데 답이 틀리는 것이 아니라 메모리 초과가 납니다.

vector 함수에서 호출할 때 거의 다 참조자로 선언해서 메모리 초과가 날 일은 없는 것 같은데 재귀함수 호출 스택이 터져도 메모리 초과가 날 수 있나요?

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector<int> vi;

int init(vi& a, vi& tree, int le, int ri, int node) //RMQ 초기화
{
    if(le==ri) return tree[node]=le;
    int mid=(le+ri)/2;
    int lidx=init(a,tree,le,mid,node*2); //좌측 서브트리  초기화
    int ridx=init(a,tree,mid+1,ri,node*2+1); //우측 서브트리 초기화

    if(a[lidx]<a[ridx]) return tree[node]=lidx;
    else return tree[node]=ridx;
}

int query(vi& a, vi& tree, int le, int ri, int st, int en, int node) //최솟값의 인덱스를 반환
{
    if(en<le || ri<st) return -1;
    if(le<=st && en<=ri) return tree[node];
    int mid=(st+en)/2;
    int lq=query(a,tree,le,ri,st,mid,node*2);
    int rq=query(a,tree,le,ri,mid+1,en,node*2+1);
    if(a[lq]<a[rq] || rq==-1) return lq;
    else return rq;
}

ll dnc(vi& a, vi& tree, int n, int le, int ri) //분할 정복 메소드
{
    int pivot=query(a,tree,le,ri,0,n-1,1); //최솟값의 인덱스를 찾음 
    ll bval=(ll)(ri-le+1)*(ll)a[pivot]; //양쪽 공통으로 찾은 히스토그램 
    ll lval=0,rval=0;
    if(le<=pivot-1)
        lval=dnc(a,tree,n,le,pivot-1); //왼쪽 히스토그램 
    if(pivot+1<=ri)
        rval=dnc(a,tree,n,pivot+1,ri); //오른쪽 히스토그램 

    ll ma=0;
    ma=max(ma,bval);
    ma=max(ma,lval);
    ma=max(ma,rval);

    return ma;
}

bool solve()
{
    int n;
    scanf("%d",&n);
    if(n==0) return false;

    int height=(int)ceil(log2(n)+1e-9);
    int tree_size=(1<<(height+1));

    vi a(n);
    vi tree(tree_size);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    init(a,tree,0,n-1,1);

    printf("%lld\n",dnc(a,tree,n,0,n-1));
    return true;
}

int main()
{
    while(solve());
    return 0;
}

chogahui05 5년 전 0

뎁스가 1만 이상이 넘어가네요. 그 정도까지 뎁스가 갈 일이 없다는 걸 생각해 본다면

어디선가 처리를 잘못 하셨을 거에요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그먼트 트리를 사용한 분할 정복] 메모리 초과가 납니다

ryute 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말