boj 1520: 내리막길

DP 문제로 보고 풀었는데 다른 분들이 실행 시간이 현저히 적어서 비교해 봐야겠음...

import java.util.Scanner;

public class Solution {
	public static int mat[][], dp[][];

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		mat = new int[row][col];
		dp = new int[row][col];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				mat[i][j] = in.nextInt();
				dp[i][j] = -1;
			}
		}

		System.out.println(getRouteNums(row - 1, col - 1, row, col));
	}

	public static int getRouteNums(int row, int col, int maxRow, int maxCol) {
		if (row == 0 && col == 0) {
			return 1;
		}
		if (dp[row][col] != -1) {
			return dp[row][col];
		}

		int left = row - 1 >= 0 && mat[row][col] < mat[row - 1][col] ? getRouteNums(row - 1, col, maxRow, maxCol) : 0;
		int right = row + 1 < maxRow && mat[row][col] < mat[row + 1][col] ? getRouteNums(row + 1, col, maxRow, maxCol): 0;
		int up = col - 1 >= 0 && mat[row][col] < mat[row][col - 1] ? getRouteNums(row, col - 1, maxRow, maxCol) : 0;
		int down = col + 1 < maxCol && mat[row][col] < mat[row][col + 1] ? getRouteNums(row, col + 1, maxRow, maxCol): 0;
		return dp[row][col] = left + right + up + down;
	}
}

 

1. bufferedReader 대신 Scanner를 쓴 점

2. getRouteNums의 4방향 값을 구할 때, dp에 있는 값이더라도 굳이 재귀함수 호출을 하게 되어 시간이 더 걸린 것 같다.