글 읽기 - 방문 조회를 왜 하는 것인지... 이해가 안 갑니다

jg3099 4년 전 0

if(ret != -1) { return ret; }

이 문장 질문이 있습니다.

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

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

그 위치까지 서로 다른 경로로 갔으니 말입니다.

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

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

#include <iostream>
#include <string.h>
#include <queue>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

long long int dp[101][101];
int board[101][101] ;
int N;

long long int solve(int x, int y){

	long long int& ret = dp[x][y];

	if(x == N && y == N){
		return 1;					
	}
	
	if(x > N || y > N){
		return 0;					
	}
	
	if(ret != -1) {
		return ret;
		
	}
	
	ret = 0;
	if( x + board[x][y] <= N){
		ret += solve(x + board[x][y], y);
	}
	if( y + board[x][y] <= N){
		ret += solve(x, y + board[x][y]);
	}
	
	return ret;	
}



int main(int argc, char** argv) {
	
	int i, j;
	int pivot = 0;
	int pop = 0;
	long long int result = 0;

	cin >> N;
	
	for(i = 1; i <= N; i++){
		
		for(j = 1; j <= N; j++){
			
			cin >> board[i][j];
		}
		
	}

	memset(dp, -1, sizeof(dp));

	cout << solve(1, 1);

	return 0;
}

kdr06006 4년 전 1

당연히 가본 곳에 또 가는 것이 맞지만, 그렇게하면 너무 많은 연산을 하게 돼 시간초과가 납니다

해당 지점에서 최고의 점수로 가는 점수를 미리 '메모'해둔다면 시간초과가 나지않습니다

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

문제

문제

출처

ICPC

방문 조회를 왜 하는 것인지... 이해가 안 갑니다

jg3099 4년 전 0

kdr06006 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말