글 읽기 - 11048 이동하기 메모리초과 or 런타임 에러

purpose 5년 전 0

메모리 초과 문제에서 메모이제이션을 이용했는데 메모리 초과가 나옵니다. 재귀함수를 많이 호출해서 나오는 것 같은데 어떻게 고쳐야 할지 모르겠네요..

조언 부탁드립니다.

if(dp[a][b] > 0){ return dp[a][b]; }를

if(a == 1 && b == 1){ return candy[1][1];의 위로 올리게 되면 런타임 에러가 나옵니다.

#include <stdio.h>

int max(int a, int b){
        if(a < b){
                return b;
        }else{
                return a;
        }
}
int n, m;
int candy[1001][1001];
int dp[1001][1001];
int recur(int a, int b){
        if(a == 1 && b == 1){
                return candy[1][1];
        }else if(a == 1){
        	dp[a][b] = recur(a, b - 1) + candy[a][b];
        }else if(b == 1){
        	dp[a][b] = recur(a - 1, b) + candy[a][b];
        }
        if(dp[a][b] > 0){
            return dp[a][b];
        }
        dp[a][b] = max(recur(a - 1, b), recur(a, b - 1)) + candy[a][b];
        return dp[a][b];
}
int main(){
        scanf("%d %d", &n, &m);
        int i, j;
        for(i = 1; i <= n; i++){
                for(j = 1; j <= m; j++){
                        scanf("%d", &candy[i][j]);
                }
        }
        printf("%d", recur(n, m));

        return 0;
}

djm03178 5년 전 1

사탕의 개수가 0일 수 있기 때문에, dp[a][b]가 이미 결정이 됐는데도 인지하지 못하고 또 계산하려 할 수 있습니다. 또한 17번째 줄이나 19번째 줄이 실행되었는데도 21번째 줄에 걸리지 않고 24번째 줄이 또 실행될 수 있습니다. 그래서 음수 인덱스로 나아갈 수 있습니다.

purpose 5년 전 0

아!! 명쾌한 답변 감사합니다 ^^

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

문제

문제

출처

ICPC

11048 이동하기 메모리초과 or 런타임 에러

purpose 5년 전 0

djm03178 5년 전 1

purpose 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말