[백준] 1890번: 점프 (Java)

💡문제 분석 요약

각 칸에 현재 갈 수 있는 거리가 적혀있는 NxN 게임판이 주어지고, 반드시 오른쪽이나 아래쪽으로 이동할 수 있다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• 이동 경로를 저장할 `dp`배열을 생성한다.
• 시작 위치인 `dp[0][0]`을 1로 설정하고, 이중 for문으로 게임판 배열을 탐색한다.
• 탐색 위치가 게임판의 가장 오른쪽 아래 칸이면 반복문을 종료한다.
• 게임판에 적혀있는 숫자만큼 오른쪽 또는 아래쪽으로 이동할 수 있으면 `dp`배열에 경로를 저장한다.

 

💡코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] gameBoard = new int[N][N];
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                gameBoard[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        long[][] dp = new long[N][N];
        dp[0][0] = 1; // start
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(i==N-1 && j==N-1) break;

                if(gameBoard[i][j]+i < N)
                    dp[gameBoard[i][j]+i][j] += dp[i][j];
                if(gameBoard[i][j]+j < N)
                    dp[i][gameBoard[i][j]+j] += dp[i][j];
            }
        }

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

 

💡시간복잡도

$O(N^2)$

 

💡 틀린 이유

`dp`배열을 long 타입으로 선언해야 하는데 int 타입을 사용했다.

 

💡 틀린 부분 수정

`dp`배열을 long 타입으로 변경했다.

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

 

💡 느낀점 or 기억할정보

문제에서 “경로의 개수는 $2^{63}-1$보다 작거나 같다.” 라는 문장이 있어 long 타입을 사용해야 한다는 것이 언급되었지만, 코드를 작성하며 이것을 잊고 int 타입으로 선언해서 틀리게 되었다.

문제에서 주어진 기억해야하는 중요한 정보도 알고리즘 설계에 작성해야 코드를 작성할 때 기억할 수 있을 것 같다.