[JAVA] 백준 1890 - 점프

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

 

솔직히 맞을줄몰랐는데 맞아서 신기했다

 

어차피 오른쪽 또는 아래로만 갈수있으므로,

그리디를 적용해서 메모이제이션으로 풀 수있었다.

 

그리디를 적용했다는것은 , 지도를 왼쪽 -> 오른쪽 , 위 -> 아래 순으로 이중 for문을 돌렸을때,

한번 방문한것은 다시 방문 안해도 되는것을 깨닫고 적용해보았다.

 

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

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));
        N = Integer.parseInt(br.readLine());
        dp = new long[N][N];
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            String[] lines = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(lines[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) {
                    System.out.println(dp[N - 1][N - 1]);
                }
                int step = map[i][j];
                if (i + step < N) {
                    dp[i + step][j] += dp[i][j];
                }
                if (j + step < N) {
                    dp[i][j + step] += dp[i][j];
                }

            }

        }

    }
}