글 읽기 - 내려가기 문제 메모리초과에 관해 질문 좀 드립니다.

postbg 9년 전 0

계속 메모리 초과가 나는데, 더이상 어디를 고쳐야 할지를 모르겠습니다.

부족한 실력에 한마디 조언부탁드립니다

#include<cstdio>
#include<iostream>

using namespace std;

const int MININF=-987654321;
const int MAXINF=987654321;

int** cache;
int** num;
int N;

int max_num(int line, int pos){
	if(line==N) return 0;

	int& ret=cache[line][pos];
	if(ret!=-1) return ret;

	ret=MININF;

	if(pos==0){
		for(int i=0; i<2; i++){
			ret=max(ret, num[line][pos]+max_num(line+1, i));
		}
	}
	else if(pos==1){
		for(int i=0; i<3; i++){
			ret=max(ret, num[line][pos]+max_num(line+1, i));
		}
	}
	else if(pos==2){
		for(int i=1; i<3; i++){
			ret=max(ret, num[line][pos]+max_num(line+1, i));
		}
	}

	return ret;
}

int min_num(int line, int pos){
	if(line==N) return 0;

	int& ret=cache[line][pos];
	if(ret!=-1) return ret;

	ret=MAXINF;

	if(pos==0){
		for(int i=0; i<2; i++){
			ret=min(ret, num[line][pos]+min_num(line+1, i));
		}
	}
	else if(pos==1){
		for(int i=0; i<3; i++){
			ret=min(ret, num[line][pos]+min_num(line+1, i));
		}
	}
	else if(pos==2){
		for(int i=1; i<3; i++){
			ret=min(ret, num[line][pos]+min_num(line+1, i));
		}
	}

	return ret;
}

int main(){

	scanf("%d", &N);

	num=new int*[N];
	cache=new int*[N];

	for(int i=0; i<N; i++){
		num[i]=new int[3];
		cache[i]=new int[3];
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<3; j++){
			scanf("%d", &num[i][j]);
			cache[i][j]=-1;
		}
	}
	int max_ans=MININF;
	for(int i=0; i<3; i++){
		max_ans=max(max_ans, max_num(0, i));
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<3; j++){
			cache[i][j]=-1;
		}
	}

	int min_ans=MAXINF;
	for(int i=0; i<3; i++){
		min_ans=min(min_ans, min_num(0, i));
	}

	printf("%d %d\n", max_ans, min_ans);

	return 0;
}

yukariko 9년 전 0

계산과정을 잘 생각해보면

cache가 꼭 모든경우에 대해 알고있어야할 필요는 없습니다.

피보나치를 예로 들어볼게요..

fibo(100) 을 구하려면 fibo(99) 와 fibo(98) 을 알아야되고 쭉 내려가다보면 1~100개가 필요합니다.

하지만 fibo(1) , fibo(2) 를 가지고 시작하면 fibo(1) 대신 1과2를가지고 만든 fibo(3)으로 대체하고, fibo(2) 를 fibo(4) 로 대체한다면

2개의 캐시만을 가지고 fibo(100)을 구할 수 있습니다. 내려가기문제도 똑같은 구조를 갖기 때문에 같은 방법으로 문제를 해결이 가능합니다.

koosaga 9년 전 0

여담이지만 배열 메모리가 300000 * 2 * 4byte = 2.4MB로 아마 아슬아슬하게 4MB 안에서 해결이 가능하지 않을까 합니다.4MB를 넘기는 이유가 재귀 함수를 사용해서 (스택 메모리라고 자세한 건 검색해보세요 ^^;)가 아닐까라고 추측하는데 재귀 함수 대신 반복문으로 해결해도 괜찮을 거 같습니다.

postbg 9년 전 0

주중에 너무 바빠서 이제서야 답글을 읽었네요

yukariko님 먼저 답변 감사드립니다. 정말 조언해주신대로 다시 생각해보니 cache크기를 확 줄일 수 있더군요.

koosaga님 역시 답변 감사드립니다. 저도 스택메모리 때문일 것이라고 생각했는데, iteration으로 바꿀 생각은 하지 못했었네요. 많이 배웠습니다.

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

문제

문제

출처

ICPC

내려가기 문제 메모리초과에 관해 질문 좀 드립니다.

postbg 9년 전 0

yukariko 9년 전 0

koosaga 9년 전 0

postbg 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말