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

 

✔ 문제

난이도 : 실버1 🥈

https://www.acmicpc.net/problem/1890

1890번: 점프

 

NxN 게임판에 수가 적혀 있습니다, 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가야 합니다.

각 칸에 적혀 있는 수만큼 오른쪽 또는 아래쪽으로 갈 수 있습니다. ( 아래로 점프, 오른쪽으로 점프 두 경우만 존재 )

가장 왼쪽 위 칸에서 가장 오른쪽 아래칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 문제입니다.

 

 

✔ 문제 풀이

처음에는 모든 경로를 구할 생각에 재귀호출을 사용하여 풀었지만 당연하게도 시간초과... 😭

그림처럼 최악의 경우 경로가 겹치게 되면 계속해서 호출이 늘어나게 됩니다.

 

겹치는 연산을 줄이면서 경로를 탐색해 나가야 합니다.

지나간 경로의 개수를 누적하여 탐색하게 되면 최종적으로 도착점에는 모든 도착 가능한 경로의 개수가 누적되어 있을 것입니다.

 

 

🔎 전체 코드

경로의 개수를 누적하여 탐색하기 위해 dp배열을 게임판과 같은 크기로 생성합니다.

이때 long형인 이유는 '경로의 개수는 2^63-1보다 작거나 같다'이기 때문에 long형으로 생성해야 합니다.

처음 시작되는 경로는 1이기 때문에 시작하는 자리인 dp[0][0] 에 초기 값 1을 설정합니다.

 

if( jump == 0 ) break

이는 마지막 도착점에 도달했다는 뜻으로 이미 이전 경로에서 결괏값이 누적되어 저장되었기 때문에 연산하지 않습니다.

만약 연산된다면 점프 거리가 0이기 때문에 제자리에서 2번 더 누적산하게 되어 정확한 결괏값이 나오지 않게 됩니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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];
        long[][] dp = new long[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());
            }
        }

        dp[0][0]=1;

        for( int i = 0; i<n; i++){
            for( int j = 0; j<n; j++){
                int jump = gameBoard[i][j];
                if( jump == 0 ) break;
                if( j+jump < n ) dp[i][j+jump] += dp[i][j];
                if( i+jump < n ) dp[i+jump][j] += dp[i][j];

            }

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

	}
}