[백준] 점프 (DP)

문제 소개

점프 - 백준 1890번 문제를 정리합니다.
이 문제는 게임판에서 오른쪽 또는 아래 방향으로만 이동하며 도달 가능한 경로의 개수를 세는 DP 유형의 문제입니다.

핵심은 "현재 위치에서 점프 칸 수만큼만 이동 가능"하고, "0이 나오는 칸은 종착점"이라는 규칙을 만족해야 합니다.

문제 링크: 점프 - 백준 1890번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 도착할 수 있는 경로 수를 저장할 dp[i][j] 배열 정의
2. 시작점 (0,0)에서 출발해, 오른쪽 또는 아래로 점프하는 방식으로 경로 누적
3. 각 칸에서 이동 가능한 거리(jump)를 읽고, i + jump 또는 j + jump 위치에 dp[i][j]를 더함
4. 0이 적힌 칸은 더 이상 점프할 수 없으므로 무시

---

해결 과정 및 코드

핵심 아이디어

1. dp[i][j]는 (0,0)부터 (i,j)까지 도달할 수 있는 경로 수를 의미
2. 모든 칸을 순회하면서 dp[i][j] > 0인 경우, 현재 칸에서 점프 가능한 거리만큼 오른쪽과 아래로 점프
3. 점프한 위치의 dp 값에 현재 dp[i][j]를 더함 (누적합)
4. 최종적으로 dp[N-1][N-1] 값이 가능한 경로의 수가 됨

코드

시간 복잡도 : O(N²)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int N = read();
        long [][] boardDp = new long[N][N];
        boardDp[0][0] = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int jump = read(); // 현재 칸의 점프 거리
                if (jump == 0) continue; // 도착 칸이거나 이동 불가 칸
                if (j + jump < N) {
                    boardDp[i][j + jump] += boardDp[i][j]; // 오른쪽으로 점프
                }
                if (i + jump < N) {
                    boardDp[i + jump][j] += boardDp[i][j]; // 아래로 점프
                }
            }
        }
        System.out.println(boardDp[N-1][N-1]);
    }

    public static int read() throws IOException {
        int cur, n = System.in.read() & 15;
        while((cur = System.in.read()) > 32){
            n = (n << 3) + (n << 1) + (cur & 15);
        }
        return n;
    }
}

참고

https://orion-log.tistory.com/97