글 읽기 - 시간초과 이유..

songjuh 7년 전 0

이렇게 하면 왜 시간초과가 나는건가요..?ㅜㅜㅜ

#include<iostream>

using namespace std;

int map[1001][1001];
int vst[1001][1001] = { 0 };
int m, n;//m은 y축 n은 x축
int maxx = 0;

void dp(int y, int x, int sum)
{
	if (x == n - 1 && y == m - 1)
	{
		sum += map[y][x];
		//cout << "끝낫어" << endl;
		if (maxx < sum)
		{
			maxx = sum;
		}
		return;
	}
	//오 밑 대각
	if (vst[y][x + 1] != 1 && x + 1 <= n - 1)//오른쪽
	{
		//cout << "오른쪽" << endl;
		vst[y][x] = 1;
		dp(y, x + 1, sum + map[x][y]);
	}
	if (vst[y+1][x] != 1 && y + 1 <= m - 1)//밑
	{
	//	cout << "밑" << endl;
		vst[y][x] = 1;
		dp(y+1, x, sum + map[x][y]);
	}
	if (vst[y+1][x + 1] != 1 && x + 1 <= n - 1&&y+1<=m-1)//대각선
	{
		//cout << "대각선" << endl;
		vst[y][x] = 1;
		dp(y+1, x + 1, sum + map[x][y]);
	}
	vst[y][x] = 0;
}


int main()
{
	cin >> m >> n;
	for (int i = 0; i < m; i++)//m y축
	{
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	}
	dp(0, 0, 0);
	cout << maxx;

}

jjwdi0 7년 전 0

지금 코드에서 dp함수는 단순한 DFS입니다.

즉 이미 탐색한 부분이 중복으로 탐색될 수 있다는 말입니다.

이미 한 번 온 점을 다시 올 필요가 없게 만드려면

어떻게 해야 할지 고민해 보시면 답에 근접하실 수 있을 것입니다.

동적계획법에 대해 조금 더 알아보시는 것도 좋을 듯 합니다.

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

문제

문제

출처

ICPC

시간초과 이유..

songjuh 7년 전 0

jjwdi0 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말