글 읽기 - 메모리 초과가 뜨는데 도움 부탁드려요!

shadowpur97 1년 전 0

25 퍼 정도에서 메모리 초과가 자꾸 뜨는데 원인을 모르겠네요.. ㅠㅠ

최소 높이를 저장하는 세그먼트 트리로 풀었습니다!

#include <iostream>
using namespace std;

typedef long long ll;

int min(const int& a, const int& b, int height[]){
  if(a == -1)
    return b;
  if(b == -1)
    return a;
  return (height[a] > height[b])? b : a;
}

ll max(const ll& a, const ll& b){
  return (a > b)? a : b;
}

ll max(const ll& a, const ll& b, const ll& c){
  return max(max(a, b), c);
}


int init_tree(int height[], int segmnt[], int start, int end, int node){
  // If we met leaf node
  if(start == end)
    return segmnt[node] = start;

  int mid = (start + end) / 2;
  return segmnt[node] = min(init_tree(height, segmnt, start, mid, node * 2 + 1),
                            init_tree(height, segmnt, mid + 1, end, node * 2 + 2), height);
}

// start, end -> range info of current node
// S, E       -> range info that we want to know
int sum_tree(int segmnt[], int height[], int start, int end, int node, int S, int E){
  if(S > end || E < start)
    return -1;

  if(S <= start && end <= E)
    return segmnt[node];

  int mid = (start + end) / 2;
  return min(sum_tree(segmnt, height, start, mid, node * 2 + 1, S, E),
             sum_tree(segmnt, height, mid + 1, end, node * 2 + 2, S, E), height);
}


ll search(int segmnt[], int height[], int start, int end, const int &N){
  int temp = sum_tree(segmnt, height, 0, N-1, 0, start, end);

  ll area = height[temp] * (end - start + 1);

  if(start == end)
    return height[start];

  if(temp == start)
    return max(area, search(segmnt, height, start + 1, end, N));

  if(temp == end)
    return max(area, search(segmnt, height, start, end - 1, N));

  return max(area, search(segmnt, height, start, temp - 1, N),
                   search(segmnt, height, temp + 1, end, N));
}



int main(){
  int N = -1;
  while(1){
    cin >> N;
    int height[N];
    int segmnt[N << 1];

    if(N == 0) return 0;

    for(int idx = 0; idx < N; idx++)
      cin >> height[idx];

    init_tree(height, segmnt, 0, N-1, 0);


    cout << search(segmnt, height, 0, N-1, N) << '\n';
  }
}

lighthouse97 1년 전 0

main()의 while 문내에 height와 segmnt 배열을 동적으로 할당해서 사용해 보세요. 사용이 끝나면 새로 할당하기 전에 제거하구요.

그리고 segmnt 배열의 크기가 잘못되어 있읍니다. N의 2배로 할당하면 필요한 만큼 할당할 수 없는 경우도 생깁니다.

byeongkeunahn 1년 전 0

lighthouse97님이 말씀해주신 부분이 맞습니다. 하지만 한 군데가 더 틀렸습니다. 그 외에는 틀린 곳은 없는 것 같습니다. 정리하면 다음과 같습니다.

세그먼트 트리는 원소 수 N의 4배로 한다고 기억하시면 됩니다. 즉, 73번 줄의 선언을 int segmnt[N << 2]로 바꿔야 합니다.
51번 줄에서 정수 오버플로우가 발생합니다. 저장은 64비트형에 하지만 중간 계산 시 32비트 곱하기 32비트여서 이미 오버플로우가 발생한 이후에 sign extension을 하여 64비트로 늘려봐야 소용이 없습니다. height[temp] * (ll)(end - start + 1)처럼 바꿔야 합니다.

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

문제

문제

출처

ICPC

메모리 초과가 뜨는데 도움 부탁드려요!

shadowpur97 1년 전 0

lighthouse97 1년 전 0

byeongkeunahn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말