글 읽기 - 시간초과문제에 관해서 질문드려요 dp초기화에대해서

zjvlzld 7년 전 0

dp초기화를 -1로 하면 잘 돌아가는데 0으로 하면 안돌아가게 되네요... 이유가 뭘까요??

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int sq[500][500];
int dp[500][500] ;


int get(int y, int x, int N, int M)
{
	int dx[4] = { 1,-1,0,0 };
	int dy[4] = { 0,0,1,-1 };
	
	if (dp[y][x]!=-1)
	{
		return dp[y][x];
	}
	if (y == N - 1 && x == M - 1)
	{
		return 1;
	}
	for (int i = 0; i < 4; i++)
	{
		if (sq[y][x] > sq[y + dy[i]][x + dx[i]] && y + dy[i] >= 0 && y + dy[i] < N && x + dx[i] >= 0 && x + dx[i] <M)
		{
			dp[y][x] += get(y + dy[i], x + dx[i], N, M);
		}
	}
	return dp[y][x];
}

int main()
{
	int x, y;
	scanf("%d %d", &y, &x);
	dp[y - 1][x - 1] = 1;
	for (int i = 0; i < y; i++)
	{
		for (int j = 0; j < x; j++)
		{
			scanf("%d", &sq[i][j]);
			dp[i][j] = -1;
		}
	}
	printf("%d", get(0, 0, y, x));
}

aung 7년 전 4

저도 방금알았는데요,

dp배열 값을 -1로 초기화 시켜놓고 값을 구했을 때 아에 목적지에 도달 불가능한 경우가 생깁니다. 그걸 dp[r][c] = 0 이라고 계산해놓는다면

다음번에 같은 위치에 재귀가 들어갔을 때, 0을 반환하게 되겠죠

그러나 dp배열 값을 0으로 초기화 시켜놓고 값을 구하면, 현재 위치에서 목적지까지의 경로가 없을 경우 또한 dp[r][c] = 0이므로 반복적으로 재귀를 호출하는 경우로 인해

시간초과가 난다는 것을 알게 되었습니다.

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

문제

문제

출처

ICPC

시간초과문제에 관해서 질문드려요 dp초기화에대해서

zjvlzld 7년 전 0

aung 7년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말