글 읽기 - 시간초과 이유

songjuh 7년 전 0

dp 개념을 습득한후 다시 코드를 짜봤는데 시간초과 나는 이유를 진짜 모르겠습니다. ㅠㅠㅠㅠ

#include<iostream>
#include<algorithm>
using namespace std;

int map[1001][1001];
long long vst[1001][1001];
int N, M;
void dfs(int y, int x)
{
	if (y == N&&x == M)
	{
		return;
	}
	if (y + 1 <= N)//하
	{	
		if (vst[y+1][x]!=0&&(vst[y + 1][x] > vst[y][x] + map[y + 1][x]))
			return;
		else 
		{
			vst[y + 1][x] = vst[y][x] + map[y + 1][x];
			dfs(y + 1, x);
		}
	}
	if (x + 1 <= M)//우
	{
		if (vst[y + 1][x] != 0 && (vst[y][x + 1] > vst[y][x] + map[y][x + 1]))
			return;
		else 
		{
			vst[y ][x+1] = vst[y][x] + map[y ][x+1];
			dfs(y, x + 1);
		}
	}
}
int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			vst[i][j] =0;
		}
	}
	vst[1][1] = map[1][1];
	dfs(1, 1);
	cout << vst[N][M];
}

zasxer 7년 전 0

재귀에서는 스택메모리의 한계가 있죠.

함수 안에 함수가 100만 번 들어가게 되니 dfs가 아닌 main 함수 안에서나 재귀함수가 아닌 일반 함수에서 dp정의를 끝내는 것을 추천할게요.

아마 재귀는 인자가 있으면 만 번 정도로 생각하시면 될 듯 합니다.

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

문제

문제

출처

ICPC

시간초과 이유

songjuh 7년 전 0

zasxer 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말