백준 : 1890 점프 (DP)

역시 아직까지 DP문제는 조금 어렵게? 느껴지는것 같다.

 

처음에는 재귀를 사용하여 풀었느나, 시간초과가 나와 다른 방법을 찾아보던 중 DP를 사용하게 되었다.

 

DP를 사용할때 헷갈렸던 부분은 해당 위치에 값을 넣을때 기준이 

 

dp[i][j + value] += dp[i][j];// 오른쪽

dp[i + value][j] += dp[i][j]; // 아래

되는 부분이 이해가 안갔다.

 

내가 생각한 DP테이블은 해당 점을 지나가는 횟수가 해당점에 기록된다고 생각했다.

하지만, 기준은 해당점에 도달할 수 있는 경로의 수를 표시하는 거였다. 

 

아래 내용을 바탕으로 나는 dp[1][1]을 4번 지나가니깐 4가 들어가야되는거 아닌가 생각했다.

하지만, 지나가는 횟수가 아니라, dp[0][0] -> dp[1][1]까지 갈수 있는 경로의 수로 2가 맞았던 것이었다.

이런 판단오류로 조금 혼동스러웠지만, 결과적으로 이해할 수 있어서 만족스러웠다. 

앞으로는 DP관련 문제를 많이 풀어보도록 해야겠다.

import java.util.*;

class Main {
	static int n, result = 0;
	static int[][] graph;
	static long[][] dp;

	public static void road(int x, int y) {
		dp[0][0] = 1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				if (dp[i][j] == 0 || (i == n - 1 && j == n - 1)) {
					continue;
				}

				int value = graph[i][j];

				if (j + value < n) { // 범위
					dp[i][j + value] += dp[i][j];// 오른쪽
				}

				if (i + value < n) {
					dp[i + value][j] += dp[i][j]; // 아래
				}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		sc.nextLine();

		// 초기화
		graph = new int[n][n];
		dp = new long[n][n];

		// 그래프입력
		for (int i = 0; i < n; i++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			for (int j = 0; j < n; j++) {
				graph[i][j] = Integer.parseInt(stArr[j]);
			}
		}

		road(0, 0);

		System.out.println(dp[n - 1][n - 1]);

	}
}