[BOJ] 백준 1890 - 점프 (자바)

DP

DP 말고 큐랑 클래스 써서 별 지랄을 하면서 풀려고 했는데 실패..

완벽히 돌아갈게 할려고 만들면 시간초과, 시간초과 안나게 만들려니 틀렸습니다..

그냥 과감히 접고 DP로 넘어왔다.

게임판의 크기가 100 * 100 이므로 전체탐색 충분히 가능하다.

단, 런타임 에러나 무슨 오류가 날지는 모르지만 

경로의 개수는 263-1보다 작거나 같다. 라는 문구가 있기때문에 

경로 개수를 찾는 DP[][] 배열은 long 으로 만들어야한다.

전체 탐색이 가능한 이유는 이동방향이 오른쪽과 아래이기 때문에 그 다음이동에 영향을 미치지 않는다. (순차적으로 접근하기 때문)

Queue를 사용할려 했을 때는 순차접근이 안되서 계속 값이 바뀔때마다 고치고 했어야 해서 시간초과 났다.

풀이

1. 0,0 부터 N,N 까지 방문하여 다음 갈곳 경로의 횟수를 추가 해준다. (dp[i][j+next], dp[i+next][j] = dp[i][j];)

2. 단 N,N일때는 경로가 추가되면 안된다. 그리고 다음 이동할 경로가 게임판을 넘어가면 안된다. ㅎ

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
class Main {
    static int N;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];
        long[][] dp = new long[N + 1][N + 1];
        String str[];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
 
            }
        }
        dp[0][0]=1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i==N-1&&j==N-1) continue;
                int next = arr[i][j];
                if (i + next < N) {
                    dp[i + next][j] += dp[i][j];
                }
                if (j + next < N) {
                    dp[i][j + next] += dp[i][j];
                }
                //print(dp);
                //System.out.println();
            }
        }
        System.out.println(dp[N-1][N-1]);
    }
    public static void print(long[][] dp){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                System.out.print(dp[i][j]+" ");
            }
        System.out.println();
        }
        
    }
}