[BOJ]1890번 : 점프

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

1890번: 점프

 

 

분류 : 다이내믹 프로그래밍

import java.io.*;
import java.util.*;

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int map[][];
    static long dp[][];
    static int[] dx = { 1, 0 };
    static int[] dy = { 0, 1 };

    public static void main(String[] args) {

        int N = sc.nextInt();
        map = new int[N][N];
        dp = new long[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        dp[0][0]++;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int dr = 0; dr < 2; dr++) {
                    int cx = i + dx[dr] * map[i][j];
                    int cy = j + dy[dr] * map[i][j];
                    if (dr == 0) {
                        if (i != N - 1 && cx < N)
                            dp[cx][j] += dp[i][j];
                    } else if (dr == 1) {
                        if (j != N - 1 && cy < N)
                            dp[i][cy] += dp[i][j];
                    }
                }
            }
        }
        out.println(dp[N - 1][N - 1]);
        out.flush();
    }
}

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str += br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

처음에는 BFS를 이용해서 풀려고 했으나 100*100 사이즈를 간과하여 시간 초과를 받았다.

그래서 DP를 통해 다시 풀어서 통과 완료..