[백준][다이나믹] 1890 점프

다이나믹 프로그래밍을 이용하여 풀이가 가능하다. 

현재위치까지 이동가능한 경우의 수(dp[x][y])를 다음 이동가능한 위치(dp[x+move][y], dp[x][y+move])에 더하여 

이동가능한 경우를 모두 더하여 준다. 

<입력 - maps[][]>

2 3 3 1

1 2 1 3

1 2 3 1

3 1 1 0

<출력 - dp[][]>

1 0 1 0 

0 0 0 0 

1 1 0 1 

1 0 1 3 

<결과>

3

	package sdk.backjun.dp;
	import java.util.Scanner;
	/**
	* 백준, 1890, 점프
	* 다이나믹 프로그래밍
	*
	* @author whitebeardk
	*
	*/
	public class Problem1890 {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int[][] maps = new int[N][N];
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	maps[i][j] = sc.nextInt();
	}
	}
	sc.close();
	// 값이 커질 수 있으므로 long 형으로 초기화
	long[][] dp = new long[N][N];
	dp[0][0] = 1;
	for (int x = 0; x < N; x++) {
	for (int y = 0; y < N; y++) {
	int move = maps[x][y];
	if (dp[x][y] == 0 || move == 0)
	continue;
	if (x + move < N) {
	dp[x + move][y] += dp[x][y];
	}
	if (y + move < N) {
	dp[x][y + move] += dp[x][y];
	}
	}
	}
	System.out.println(dp[N - 1][N - 1]);
	}
	}

view raw Problem1890.java hosted with ❤ by GitHub

https://www.acmicpc.net/problem/1890