[Algorithm] 백준 DP문제 - 점프(1890) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 점프 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1890

1890번: 점프

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        Jump jump = new Jump(n);
        for (int row = 0; row < n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++)
                jump.setMap(row, col, parseInt(st.nextToken()));
        }
        
        jump.run();
        System.out.println(jump.getPath());
    }
}

class Jump {
    int n;
    int[][] map; // 점프 값 저장
    long[][] dp; // 점프 후 dp 저장 2^63 - 1까지 저장 될 수 있으므로
    
    Jump (int n) {
        this.n = n;
        map = new int[n][n];
        dp = new long[n][n];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value; // 좌표에 맞는 값 설정하기
    }
    
    void run() {
        dp[0][0] = 1; // 초기 값 설정

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {

                int d = map[row][col];
                if (d == 0) continue; // 만약 이동 거리가 0이라면 중복 저장을 막기 위함 dp[row][col + 0] += dp[row][col] 방지

                if (isValid(row, col + d)) { // 값만큼 열 점프
                    dp[row][col + d] += dp[row][col];
                }

                if (isValid(row + d, col)) { // 값만큼 행 점프
                    dp[row + d][col] += dp[row][col];
                }
            }
        }
    }
    
    boolean isValid(int row, int col) { // 유효한 인덱스
        return row >= 0 && row < n && col >= 0 && col < n;
    }

    long getPath() { // 마지막 0의 종료점 좌표
        return dp[n - 1][n - 1];
    }

}

 

2. 풀이 중점 사항

 

DP로 해결하므로 빅오(n^2) = (100 * 100)으로 문제를 해결할 수 있습니다.

중점 사항은 d == 0이 될 때, += 의 성질로 인해 같은 값이 중복 저장될 수 있습니다.

따라서, map[row][col] == 0이라면 해당 로직은 건너뛰어서, 값의 중복 저장을 막아야 합니다.

 

자세한 풀이는 주석화 하였습니다. 감사합니다.!