글 읽기 - 메모리초과.. dp+dfs

gkseofla7 1년 전 0

dp + dfs를 사용했는데 왜 메모리 초과나는지 모르겠네요.. 고수님들 도와주세요..ㅠ

#include<iostream>
#include<string.h>
#include<string>


using namespace std;
int n;
int arr[505][505];
int total[505][505];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0, 1, -1 };

int DFS(int x, int y)
{

	int ans = 0;//나에서 출발하니 가면 한번~
	if (total[x][y] != -1)
	{
		return total[x][y];
	}

	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n)
			continue;
		if (arr[nx][ny] < arr[x][y])//가는곳이 더 적으면
			continue;

		if (total[nx][ny] != -1)//이번에 온곳인지 아니면 이전꺼에서 와서 아는건지 어찌아냐..
		{
			ans = max(ans, total[nx][ny] + 1);
		}
		else
		{
			ans = max(ans, DFS(nx, ny) + 1);

		}
		total[x][y] = ans;//여기서 출발했을때 최대값!
	}

	return ans;//아예 못가면 그냥 0~
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
			total[i][j] = -1;
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int tmp = DFS(i, j);

			ans = max(tmp, ans);
		}

	}

	cout << ans + 1;


}

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

문제

문제

출처

ICPC

메모리초과.. dp+dfs

gkseofla7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말