글 읽기 - [2096] 메모리 초과 어떻게 해결해야 할지 모르겠어요..

alohajihwan 8년 전 0

답은 나오는데 메모리 초과로 문제를 못 풀고 있습니다..

cache[100010][5] 자체가 메모리를 약 3.7MB 정도 차지하는 것을 알고 있습니다. 그렇다면 cache 배열 없이 반복적 dp를

어떻게 푸는 건가요?

#include<stdio.h>
#include<iostream>
//#include<vector>

using namespace std;

int n;
int map[100011][5];
int cache[100011][5]; // 0로 초기화
//int cache2[100011][5];
// now = 1,2,3 이고 line 은 몇 번째 줄 인지 반환
//solve = line 줄의 now 위치에서 n까지 내려 갈때 최대합
int solve(int line, int now)
{
	//if(line > n+1) return 0;

	if(line == n) return map[line][now];

	int & ret = cache[line][now];

	if(ret != -1) return ret;
	
	// 왼쪽
	if(map[line+1][now-1] != -1)
	{
		ret = max(ret,solve(line+1,now-1) + map[line][now]);
	}

	// 아래
	ret = max(ret,solve(line+1,now) + map[line][now]);


	// 오른쪽
	if(map[line+1][now+1] != -1)
		 ret = max(ret,solve(line+1,now+1) + map[line][now]);

	return ret;
}

#define INF 99999
int solve2(int line, int now)
{
	if(line == n) return map[line][now];
	int & ret = cache[line][now];

	if(ret != INF) return ret;
	
	// 왼쪽
	if(map[line+1][now-1] != -1)
	{
		ret = min(ret,solve2(line+1,now-1) + map[line][now]);
	}

	// 아래
	ret = min(ret,solve2(line+1,now) + map[line][now]);


	// 오른쪽
	if(map[line+1][now+1] != -1)
		 ret = min(ret,solve2(line+1,now+1) + map[line][now]);

	return ret;
}
int main()
{
	cin >> n;

	for(int i=0;i<=n+1;i++)
	{
		for(int j=0;j<=4;j++)
		if(i == 0 || i == n+1 || j == 0 || j == 4) map[i][j] = -1; // 경계는 모두 -1값 넣기
		else scanf("%d",&map[i][j]);
	}

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

	printf("%d ",solve(0,2)+1);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<5;j++)
		{
			cache[i][j] = INF;   //메모리 초과를 염두해 cache배열 재활용
		}
	}

	printf("%d\n",solve2(0,2)+1);
}

slanjdu 8년 전 2

힌트는 cache배열의 값들을 모두저장해서 가지고 가지 않아도 된다! 입니다.

alohajihwan 8년 전 0

답변 감사합니다!!! 주어진 메모리가 너무 작네요ㅎㅎ 힌트 이용해서 다시 풀겠습니다!

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

문제

문제

출처

ICPC

[2096] 메모리 초과 어떻게 해결해야 할지 모르겠어요..

alohajihwan 8년 전 0

slanjdu 8년 전 2

alohajihwan 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말