• 백준 1890번 점프 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 8. 15. 17:41
    반응형

    이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.

    본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.

    그리하여 동적계획법으로 문제를 접근했다.


    N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

    각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.

    가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.


    각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개수를 업데이트 해나간다.


    for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int dist = map[i][j]; int down = dist + i; int right = dist + j; // 아래 if (down < n) { dp[down][j] += dp[i][j]; } // 오른쪽 if (right < n) { dp[i][right] += dp[i][j]; } } }


    사실상 모든 칸을 완벽히 돌 필요는 없다.

    거를 수 있는 건 거르면 된다.

    예를 들어, (1, 1)에서 오른쪽으로 3칸 이동하면 (1, 4) 가 된다.

    (1, 2), (1, 3) 은 사실상 어떠한 경우라도 필요 없는 칸이 된다. (오른쪽과 아래쪽만 거리값을 통해 이동하기 때문)


    for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dp[i][j] == 0 || (i == n - 1 && j == n - 1)) { continue; } // ........... } }


    1. dp[i][j] == 0 

    => 위에서 말한 거르는 경우


    2. i == n - 1 && j == n - 1

    => 마지막 도착 지점에서는 더이상 이동할 필요가 없다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    private void solve() {
        int[][] map = new int[101][101];
        long[][] dp = new long[101][101];
        int n = sc.nextInt();
     
        dp[0][0= 1;
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == || (i == n - && j == n - 1)) {
                    continue;
                }
     
                int dist = map[i][j];
                int down = dist + i;
                int right = dist + j;
     
                if (down < n) {
                    dp[down][j] += dp[i][j];
                }
     
                if (right < n) {
                    dp[i][right] += dp[i][j];
                }
            }
        }
        System.out.println(dp[n - 1][n - 1]);
    }
    cs


    반응형

    댓글

Designed by Tistory.