[백준] 점프 (!) (1890번 JAVA) / DP

[백준] 점프 (!) (1890번 JAVA) / DP

---

[ 접근 방법 ]

 

게임 판에 적혀있는 '이동 가능 거리' 를 arr 2차원 배열에 저장

해당 좌표까지 도착 할 수 있는 방법 수 를 DP 2차원 배열에 저장

 

좌표 (1, 1) 부터 (N, N) 까지 DP 시작 한다.

 

예제로 설명한다면,

 

[입력값]

 

[DP 출력]

DP의 (1,1)을 초기값으로 1로 설정한다.

(1, 1)에서 '이동 가능 거리'는 ' 2 ' 이다.

 

(1, 1) -> (3, 1)

(1, 1) -> (1, 3)

 

으로 이동 가능하다.

 

이와 같은 방법으로 한다면,

위와 같은 DP 출력 값이 나오게 된다.

---

[ JAVA 코드 ]

// 1890번 점프
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][N+1];
        for(int i=1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 좌표 별 가능한 경로 수
        long[][] DP = new long[N+1][N+1];
        DP[1][1] = 1;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                int next = arr[i][j];

                // 도착점
                if (next == 0) break;
                if (i + next <= N){
                    DP[i+next][j] += DP[i][j];
                }
                if (j + next <= N){
                    DP[i][next+j] += DP[i][j];
                }
            }
        }
        bw.write(DP[N][N] + "\n");

        bw.flush();
        
        bw.close();
        br.close();
    }
}

---

[ Rewind ]

1. 어려웠던 점

 

- DP 접근 방식을 고려하지 못함. (정방향이 아닌 역방향으로 도착 지점부터 출발지정까지 역방향만 고려함)

- DP 점화식을 생각하지 못함.

 

2. 알게 된 점

 

- DP에 해당 좌표까지 올 수 있는 방법 수를 저장하는 것 에 대한 방법