글 읽기 - 메모리 초과를 어떻게 해결해야하나요

dsa2341 4년 전 0

dp 재귀를 이용해서 해봤는데 메모리 초과를 어떻게 해결해야할지 모르겠습니다

#include <iostream>
#include <memory.h>
using namespace std;
int n, board[101][101];
long long dp[101][101];
int solve(int y, int x) {
	if (y >= n || x >= n) return 0;
	if (y == n - 1 && x == n - 1) return 1;
	if (dp[y][x] != -1) return dp[y][x];
	int jumpsize = board[y][x];
	dp[y][x] = (solve(y + jumpsize, x) + solve(y, x + jumpsize));
	return dp[y][x];
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> board[i][j];
	memset(dp, -1, sizeof(dp));
	long long  res = solve(0, 0);
	cout << (res == -1 ? 0 : res);
	return 0;
}

chogahui05 4년 전 0

모든 칸이 0일 땐 어떻게 동작하나요?

dsa2341 4년 전 0

아 그 경우를 생각 못했네요 틀렸지만 덕분에 메모리초과 문제점은 해결했네요 감사합니다

jg3099 4년 전 0

if (dp[y][x] != -1) return dp[y][x];

이 문장 질문이 있습니다.

이미 가 봤던 위치에는 가지 않는다는 의미로 저는 해석을 했는데요.

문제내용이 모든 경우의 수를 따지라 했으니, 가봤던 위치에 또 가는 것이 맞지 않나요?

다른 분들 질문이나 풀이를 보아도 다 저 문장이 있는데 저는 해석이 안되네요...

왜 가본 곳에 안 가는 것인가요?

dsa2341 4년 전 0

중복해서 계산하는 경우를 방지하기위함으로 알고있습니다

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

문제

문제

출처

ICPC

메모리 초과를 어떻게 해결해야하나요

dsa2341 4년 전 0

chogahui05 4년 전 0

dsa2341 4년 전 0

jg3099 4년 전 0

dsa2341 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말