[백준] 점프 : 1890 : Java - DP (S1)

1.  💎 문제

1890번: 점프

---

 

 

2.  🤔 어떻게 풀까

현재 위치에서 이동할 수 있는 경우의 수는 2가지 뿐이다. 오른쪽 또는 아래로 현재 칸에 적혀있는 수만큼 이동하는 것이다.

그러므로 위치마다 2가지 경우를 고려하여 경우의 수를 누적한다.

 

코드가 짧아 바로 전체 코드로 간다.

 

 

3.  🖥️  전체 코드

행렬의 순서대로 요소를 탐색한다. 현재 칸에 적혀있는 수만큼 오른쪽, 아래로 이동하여 이동한 위치의 경우의 수를 증가시킨다.

		int length = (int)map[i][j];
                if(i+length < N)
                    dp[i+length][j] += dp[i][j];
                if(j+length <N)
                    dp[i][j+length] += dp[i][j];

전체가 탐색이 완료 되면 각 위치에 올 수 있는 모든 경우의 수가 저장되며, 결과를 출력한다.

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


class Main
{

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        long [][] map = new long[N][N];
        long [][] dp = new long[N][N];
        dp[0][0] = 1L;

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(i == N-1 && j== N-1){
                    break;
                }
                int length = (int)map[i][j];
                if(i+length < N)
                    dp[i+length][j] += dp[i][j];
                if(j+length <N)
                    dp[i][j+length] += dp[i][j];
            }
        }
        bw.write(dp[N-1][N-1]+"\n");

        bw.flush();

        bw.close();
        br.close();

    }

}