[백준] 1890번: 점프 - java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][n];
		long[][] dp = new long[n][n];

		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(input[j]);
			}
		}

		int answer = 0;

		// 시작지점의 경로개수는 1
		dp[0][0] = 1;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				
				// 도착지점
				if (i==n-1 && j==n-1) {
					break;
				}
				int cnt = arr[i][j]; // 한 번에 이동할 칸의 개수
				
				// 아래로 이동
				if (i+cnt<n) {
					dp[i+cnt][j] += dp[i][j];
				}
				
				// 오른쪽으로 이동
				if (j+cnt<n) {
					dp[i][j+cnt] += dp[i][j];
				}
			}
		}

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

}

 

Queue 를 이용한 BFS 를 시도했지만, 시간 초과로 실패한 문제이다.

 

이 문제의 경우, 항상 오른쪽 or 아래로만 이동하므로 지나온 길을 다시 방문할 일이 전혀 없다.

따라서 dp로 풀 수 있음을 인지했다.

 

dp[x][y] => x,y 까지 도달할 수 있는 경우의 수를 뜻한다.

따라서 dp[0][0] = 1 로 초기화한다.  

(x,y)에서 오른쪽 or 아래로 이동했을 때, 이동한 위치가 범위 안이라면,

dp[nx][ny] += dp[x][y] 가 될 것이다.

즉, (nx,ny) 까지 도달하는 경우의 수에 (x,y) 까지의 경우의 수를 더해 갱신해준다.

 

 이러한 방법으로 종착지 n-1,n-1 까지의 경우의 수는 dp[n-1][n-1] 이 될 것이다.