글 읽기 - 시간초과를 피하려면 어떻게 수정해야 할까요?

thddudgns79 3년 전 0

DFS + DP로 풀었습니다. 제출하면 시간초과가 나오는데 코드를 어떻게 수정해야 시간초과를 피할 수 있을까요?

import java.util.*;

public class Main {
	static int n;
	static int m;
	static int[][] board;
	static long[][] dp;
	static boolean[][] visit;
	static int[] dx = { 0, 0, 1 };
	static int[] dy = { -1, 1, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		board = new int[n][m];
		dp = new long[n][m];
		visit = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = sc.nextInt();
				dp[i][j] = -1;
			}
		}
		visit[0][0] = true;
		long ans = dfs(0, 0);
		System.out.println(ans);

	}

	public static long dfs(int nowx, int nowy) {
		if(nowx == n - 1 && nowy == m - 1)
			return board[nowx][nowy];
		
		if(dp[nowx][nowy] != -1)
			return dp[nowx][nowy];
		
		dp[nowx][nowy] = -100000001;
		for(int dir = 0; dir < 3; dir++) {
			int nx = nowx + dx[dir];
			int ny = nowy + dy[dir];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(!visit[nx][ny]) {
				visit[nx][ny] = true;
				dp[nowx][nowy] = Math.max(dp[nowx][nowy], dfs(nx, ny) + board[nowx][nowy]);
				visit[nx][ny] = false;
			}
		}
		
		return dp[nowx][nowy];
	}

}

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

문제

문제

출처

ICPC

시간초과를 피하려면 어떻게 수정해야 할까요?

thddudgns79 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말