boj 1890: 점프

(1, 1) -> (n, n)으로 가는 경로의 개수를 구하는 문제이다.

DP[i][j] = (i, j) 칸에 갈 수 있는 경로의 개수라고 하면 DP[1][1] = 1로 초기화한다.

 

(i, j)는 오른쪽 또는 아래로 이동하므로 (i+arr[i][j], j) 또는 (i, j+arr[i][j])로 이동한다.

 

총 시간 복잡도는 N^2 칸 * O(1) 이므로 O(N^2)이다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int arr[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] = in.nextInt();
			}
		}

		long dp[][] = new long[n + 1][n + 1];
		dp[1][1] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {

				if (arr[i][j] == 0) {
					continue;
				}

				if (i + arr[i][j] <= n) {
					dp[i + arr[i][j]][j] += dp[i][j];
				}
				if (j + arr[i][j] <= n) {
					dp[i][j + arr[i][j]] += dp[i][j];
				}

			}
		}
		System.out.println(dp[n][n]);
	}
}