[백준] 1890. 점프

문제 링크

[백준] 1890. 점프

풀이 과정

입력 예)
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

위 입력 예시로 가장 오른쪽 아래 칸에 도달하는 경로는 다음과 같습니다.

위와 같이 각 좌표는 위로부터 혹은 왼쪽으로부터 도달할 수 있습니다. 메모이제이션을 위한 2차원 배열 dp를 생성한 뒤, 각 요소에는 해당 좌표까지 도달할 수 있는 경로의 가짓수를 저장해 둡니다.

if (inRange(i, j + map[i][j])) {
    dp[i][j + map[i][j]] += dp[i][j];
}

if (inRange(i + map[i][j], j)) {
    dp[i + map[i][j]][j] += dp[i][j];
}

점프 거리를 더한 다음 좌표가 맵을 벗어나지 않는다면, 점프한 다음 좌표의 dp 배열 요소에 현재 좌표까지의 경로 수를 누적시킵니다.

코드

import java.util.Scanner;

public class Main {
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int[][] map = new int[N][N];
        long[][] dp = new long[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();

        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;

                if (inRange(i, j + map[i][j])) {
                    dp[i][j + map[i][j]] += dp[i][j];
                }

                if (inRange(i + map[i][j], j)) {
                    dp[i + map[i][j]][j] += dp[i][j];
                }
            }
        }

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

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > N - 1) return false;
        return true;
    }
}