백준 1890번: 점프

문제 설명

• https://www.acmicpc.net/problem/1890
• 자신이 밟은 판에 적힌 숫자만큼 오른쪽 또는 아래로만 이동할 수 있습니다.

접근법

• BFS로 문제를 풀면 메모리 초과가 발생합니다.
  • 100x100배열의 모든 값이 1이면 대략 2^10000개의 값이 큐에 들어갔다 나와야 합니다.
• DP를 떠올리는 게 문제 해결의 핵심입니다.
  • 어떤 칸 A에 도달할 수 있는 방법이 a개이고 어떤 칸 B에 도달할 수 있는 방법이 b개일 때,
    어떤 칸 C에 도달할 수 있는 방법이 A를 거치는 것과 B를 거치는 것 두 가지만 가능하다면
    C에 도달할 수 있는 방법은 a+b개 입니다.
• 경로의 개수가 최대 2^63-1이기 때문에 int가 아닌 long을 사용해야 합니다.
  • 2^10이 1024이기 때문에 대략 1000^6 = 1_000_000_000_000_000_000 보다 큰 숫자로 int 범위를 넘어섭니다.

pseudocode

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		moveCnt = 현재 칸에서 점프해야 하는 칸의 개수
        if(오른쪽으로 이동할 수 있다면){
        	dp[i + moveCnt][j] += dp[i][j];
        }
        if(아래로 이동할 수 있다면){
        	dp[i][j + moveCnt] += dp[i][j];
        }
    }
}

정답

import java.util.*;

public class Main {
	static int[] dx = { 0, 1 };
	static int[] dy = { 1, 0 };
	static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int[][] board = new int[N][N];
		long[][] dp = new long[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		dp[0][0] = 1;
		System.out.println(dp(board, dp));

	}

	public static long dp(int[][] board, long[][] dp) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int moveCnt = board[i][j];
				if (i == N - 1 && j == N - 1) {
					return dp[N - 1][N - 1];
				}
				if (i + moveCnt < N) {
					dp[i + moveCnt][j] += dp[i][j];
				}
				if (j + moveCnt < N) {
					dp[i][j + moveCnt] += dp[i][j];
				}

			}
		}

		return -1;

	}

}

기타

함께 풀어보면 좋은 문제

• https://www.acmicpc.net/problem/1520
• https://www.acmicpc.net/problem/3114