글 읽기 - 시간초과가 뜨고 안뜨고의 차이가 궁금합니다.

apdh25 4년 전 0

이 소스의 34번째줄의

if (~dp[x][y])

return dp[x][y];

여기서 ~dp[x][y] 이부분을 예를들어 dp[x][y] ==0 이라든지 !dp[x][y]로 하면

7%에서 더이상 진행되지않고 시간초과가 뜹니다.

방문한 지점일경우에 반환해서 시간을 줄여주는 코드이기에 방문지점은 dp값이 0일줄예상하고 코드를 짯는데

꼭 저렇게 비트연산자~ 를 써야만 통과가되는 이유가 정말 궁금합니다 ㅠ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int idx1[] = { 0,0,1,-1 };
const int idx2[] = { 1,-1,0,0 };

int N, M;
int board[505][505];
int dp[505][505];

void init()
{
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%d", &board[i][j]);
			dp[i][j] = -1;
		}
	}
}

int dfs(int x, int y)
{
	if (x == N && y == M) {
		return 1;
	}

	if (~dp[x][y]) 
		return dp[x][y];

	dp[x][y] = 0;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + idx1[i];
		int ny = y + idx2[i];

		if (board[nx][ny] && board[x][y] > board[nx][ny])
			dp[x][y] += dfs(nx, ny);
	}
	return dp[x][y];
}

int main()
{
	init();
	cout << dfs(1,1) << endl;
	return 0;
}

apdh25 4년 전 0

자문자답입니다. dp값이 -1인 경우, 즉, 한번도 방문안한지점의경우 0으로 초기화하기위해 추가한 코드였네요.

아직 문제에대한 이해가 부족한가봅니다.

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

문제

문제

출처

ICPC

시간초과가 뜨고 안뜨고의 차이가 궁금합니다.

apdh25 4년 전 0

apdh25 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말