[Java] 백준 1890번 : 점프

1. 문제

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

1890번: 점프

 

 

2. 풀이 과정

처음엔 DFS로 모든 경로를 처음부터 끝까지 탐색하도록 했고, 시간 초과가 났다.

아래 그림과 유사하게, 출발점에서 도달할 수 있는 좌표에 +1을 해나가며 값을 업데이트하고 결과는 (N, N)의 값을 출력해주면 된다.

 

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

public class Main {
    static int N;
    static int[][] map;
    static long[][] dp;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solve();
        System.out.println(dp[N-1][N-1]);
    }

    public static void solve() {
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j] == 0){ continue;}
                int right = j + map[i][j];
                int down = i + map[i][j];

                if(right < N){
                    dp[i][right] += dp[i][j];
                }
                if(down < N){
                    dp[down][j] += dp[i][j];
                }
            }
        }
    }
}

 

 

결과