(1890) 점프

문제

문제
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

---

문제풀이

초반에는 dp를 사용하기 보다는 완전 탐색으로 처리하여서 접근을 먼저 해보고자 했던 문제이다. 점화식으로 처리 되면서 잘 진행이 되어 기쁘게 제출했다가 시간초과로 인해 다시 dp로 풀게 되었던 문제이지만 생각보다 많은 것을 더욱 확실하게 알게 해준 문제였다고 생각한다. 

 

기본적으로 dp 용 배열과 board용 배열 두개를 만들어 놓고 시작하여야 하는 문제이다. 그리고 다음 반복문으로 넘어가는 조건은 가로 i값과 세로 j 값이 board 끝에 도달하는 경우 또는 dp 값에 0으로 되어진 값에 있을 때, 다음으로 넘어 가야한다.

 

왼쪽은 dp, 오른쪽은 board

현재 board에 0,0에 말이 있다고 생각해보자, 현재 오른쪽으로 2칸 아래로 2칸이 이동가능하다. 그렇다면 그러한 값을 move로 받아서 (row + 2 , 0) 그리고 (0 , col + 2) 위치에 현재의 dp 값을 입력한다. 이러한 과정을 거치면 아래와 같이 변경된다. 

그 다음은 말을 이동해야하는데 2중 for문 이기 때문에 오른쪽을 먼저 순회해야 한다. 순차적으로 1씩 증가하면서 해당 위치에 있는 dp 값이 0이면 다음으로 넘어가고 0이 아닌 값에 말이 멈추게 된다. 

 

그럼 여기서는 값이 3이 나오게 되는데 오른쪽은 장외이고 아래쪽만 이동이 가능하기 때문에 (row + 3 , 3) 위치에 현재 dp 값을 입력 한다. 

 

 

그럼 현재 위치는 아직 1번째 행의 3열에 있는데, 반복문을 계속 진행하게되면 3번째 행, 1열에 있던 1을 만나게 된다. 해당 값을 dp 에 적용하면 아래와 같다. 

그다음 오른쪽으로 한칸 이동하면 방금 입력한 1이 있는데 해당 값도 적용한다. 

 

오른쪽 마지막으로 이동하면 또 다시 1이 있고 그것을 적용하면 마지막 목적지에 도착한다. 

그렇다면 마지막 줄에 있는 값들을 다 적용하게 되면 최종적으로 3이라는 값이 생기게 되고 해당값을 리턴하면 답이된다. 

---

나의 답안

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] board = new int[n+1][n+1];
        long[][] dp = new long[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        dp[1][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j] == 0 || (i == n && j == n)) continue;

                int right = board[i][j];
                int down = board[i][j];

                if (i + down <= n) {
                    dp[i+down][j] += dp[i][j];
                }

                if (j + right <= n) {
                    dp[i][j+right] += dp[i][j];
                }
            }
        }

        System.out.println(dp[n][n]);
    }
}