글 읽기 - 2096 메모리 초과

luxs1t 8년 전 0

사실상 top down 으로 안풀고 바텀업으로 풀 수 있는 문제인데

메모리 초과가 나서 사실상 껍데기만 top down 인 아래와 같은 코드를 짰습니다.

여전히 메모리 초과가 나서 질문 드립니다.

아래 코드에서 드는 메모리는 재귀호출에 따른 스택에 쌓이는 메모리 + 각 함수 내부에서 로컬하게 쓰는 int rows[3]; 분에 해당하는 메모리.

이렇게가 다인 것 같은데.. 다른분 탑다운으로 짜신분의 매우 귀한 코드를 보면 저랑 비슷하게 메모리를 들이신 것 같은데 어디서 초과가 날까요..

혹시 나는 부분이 있으면 알려주시면 감사하겠습니다~

#include <iostream>
using namespace std;
#define MAX_VALUE 9000000
 
int n;
int dp_max[3];
int dp_min[3];
int temp[3];
 
void solve(int cur) {
    int rows[3];
    for (int i=0;i<3;i++) scanf("%d", &rows[i]);
 
    if (cur == n-1) {
        dp_min[0] = rows[0];
        dp_min[1] = rows[1];
        dp_min[2] = rows[2];
 
        dp_max[0] = rows[0];
        dp_max[1] = rows[1];
        dp_max[2] = rows[2];
        return;
    }
    else {
        solve(cur+1);
        temp[0] = rows[0] + min(dp_min[0], dp_min[1]);
        temp[1] = rows[1] + min(min(dp_min[1], dp_min[0]), dp_min[2]);
        temp[2] = rows[2] + min(dp_min[2], dp_min[1]);
         
        dp_min[0] = temp[0];
        dp_min[1] = temp[1];
        dp_min[2] = temp[2];
         
        temp[0] = rows[0] + max(dp_max[0], dp_max[1]);
        temp[1] = rows[1] + max(max(dp_max[1], dp_max[0]), dp_max[2]);
        temp[2] = rows[2] + max(dp_max[2], dp_max[1]);
         
        dp_max[0] = temp[0];
        dp_max[1] = temp[1];
        dp_max[2] = temp[2];        
        return;
    }
}
 
int main() {
     
    scanf("%d", &n);
    solve(0);
    int max_ans = max(max(dp_max[0], dp_max[1]), dp_max[2]);
    int min_ans = min(min(dp_min[0], dp_min[1]), dp_min[2]);
    printf("%d %d\n", max_ans, min_ans);
    return 0;
}
소스코드 공개      공개      비공개      맞았을 때만 공개     수정
다운로드

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

문제

문제

출처

ICPC

2096 메모리 초과

luxs1t 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말