백준 1890 - 점프

문제

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

리뷰

전형적으로 DP를 사용하여 풀이하는 문제였다. 처음에 문제 조건을 제대로 파악하지 못해
0을 만나면 방문을 중지해야 하는 처리를 하지 않아 시간 초과를 계속 마주했었다.

한 지점에서 다른 지점으로 이동하게 될 경우 문제에서 주어진 이동 방향(오른쪽, 아래)상
방문한 지점을 재방문 하지 않기에 이미 갱신된(초기값 -1이 아닌) dp 값을 활용하여
빠르게 연산을 처리할 수 있는 점이 로직을 구성함에 있어 가장 중요한 부분이었다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[][] values;
    static long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = parseInt(st.nextToken());
        values = new int[N][N];
        dp = new long[N][N];

        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++) {
                values[y][x] = parseInt(st.nextToken());
                dp[y][x] = -1;
            }
        }

        System.out.println(recur(0, 0));
        br.close();
    }

    static long recur(int x, int y) {
        if (x >= N || y >= N) return 0;

        if (x == N - 1 && y == N - 1) return 1;

        if (values[y][x] == 0) return 0;

        if (dp[y][x] != -1) return dp[y][x];

        return dp[y][x] = recur(x + values[y][x], y) + recur(x, y + values[y][x]);
    }
}

결과