[BOJ] 1890 - 점프

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1890

1890번: 점프

난이도: 실버 2

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍을 이용해 쉽게 해결할 수 있습니다. 다이나믹 프로그래밍을 위한 배열을 하나 만들고, 이 배열에 해당 칸까지 올 수 있는 경우의 수를 저장해주면 됩니다.

 

 

주어진 예제를 이용해보겠습니다. (0, 0)에 2가 들어가 있습니다. 그렇다면, 우측으로 2칸 점프하거나, 아래 방향으로 2칸 점프하는 경우의 수밖에 없습니다. 따라서, dp[0][2]에 1을 더해주고, dp[2][0]에 1을 더해주면 됩니다. (0, 0)에 올 수 있는 경우의 수가 1 뿐이어서 dp[0][0]에 1을 미리 넣어두었기 때문입니다. (0, 0)을 제외한 dp 배열은 반복문을 통해 채워지게 됩니다. 가장 마지막 칸에 도착할 때까지 반복문을 수행하면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        N = Integer.parseInt(br.readLine());
 
        int i,j;
        String s;
        StringTokenizer st;
        int [][]arr = new int[N][N]; // 입력을 저장하기 위한 배열
        long [][]dp = new long[N][N]; // dp를 위한 배열
        for(i=0;i<N;i++){
            s = br.readLine();
            st = new StringTokenizer(s);
            for(j=0;j<N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        dp[0][0] = 1; // 첫칸에 올수있는 경우의 수는 하나 뿐
        for(i=0;i<N;i++){
            for(j=0;j<N;j++){
                if(i==N-1 && j==N-1) // 마지막 칸에 도달했다면 종료 (마지막 칸의 입력은 0이기 때문에 자기 자신에게 특정 값을 더하는 일을 막기 위해)
                    break;
                if(dp[i][j] != 0){
                    if(i+arr[i][j] < N){ // 아래쪽으로 점프하는 경우
                        dp[i+arr[i][j]][j] += dp[i][j]; // 자신에게 올 수 있는 경우의 수를 점프할 칸의 dp배열에 더해준다.
                    }
                    if(j+arr[i][j] < N){ // 오른쪽으로 점프하는 경우
                        dp[i][j+arr[i][j]] += dp[i][j];
                    }
                }
            }
        }
        System.out.println(dp[N-1][N-1]);
    }
}

 

참고로 문제에서 int 자료형의 범위를 벗어나는 경로의 수가 있을 수 있다고 언급되어 있기 때문에 dp 배열은 long 자료형으로 선언했습니다. 실제로 int로 dp를 선언하고 채점을 돌리면 틀렸다는 답을 받게됩니다.