[BOJ] 1890 점프 - JAVA

1. 문제

1890번: 점프

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  왼쪽 맨 위에서 시작하기 때문에 항상 그 위치는 경우의 수가 1이다. dp[0][0]에 1을 저장해두고 시작한다.

2.  하나씩 숫자를 입력받으면서 탐색을 진행한다.

3.  만약 dp[i][j]가 0이라면 다음으로 이동할 필요 없다. [i+숫자][j]와 [i][j+숫자]에 0을 더해봤자 그 숫자 그대로이기 때문이다.

4.  tmp가 0일때도 다음으로 이동하지 않는다. 문제에 0은 종착지라고 써있다. 0은 어디로도 이동할 수 없다.

5.  i, j에 각각 tmp를 더해서 범위에 벗어나지 않는다면 현재 dp[i][j]값을 더한다.

6.  마지막에 dp[N-1][N-1]을 출력한다.

import java.io.*;
import java.util.*;

public class BOJ_1890_점프 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());

      long[][] dp = new long[N][N];
      dp[0][0] = 1;

      StringTokenizer st;
      int tmp;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<N;j++){
            tmp = Integer.parseInt(st.nextToken());
            if(dp[i][j] == 0 || tmp==0) continue;
            if(j+tmp < N) dp[i][j+tmp] += dp[i][j];
            if(i+tmp < N) dp[i+tmp][j] += dp[i][j];
         }
      }

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

---

3. 결과

답이 2^63-1까지 가능하기 때문에 dp를 long타입으로 선언해야 한다.