BOJ#1520 내리막 길

BOJ#1520 내리막 길

* 문제

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

* 풀이

무심코 풀었다가 틀린 원인을 찾지 못해서 고생한 문제입니다.

주의해야 할 점으로는

내리막길로 이동하다가 중간에 멈추는 경우가 생길 수 있는데

이 때 dp값은 0이 되어야 할 것입니다.

그런데 dp 초기값을 0으로 설정한 경우 

위 경우를 처리할 수 없어 memoization을 하지 못하고 다시 연산을 해야하므로 시간초과가 발생하게 됩니다.

따라서 dp 초기값을 위 경우(0)를 처리할 수 있는 값으로 설정해야 합니다. (예: -1)

∴ dp 초기값 설정 시 주의할 것

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231520_Downhill/src/Main.java

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

/**
 * BOJ#1520 내리막길
 * https://www.acmicpc.net/problem/1520
 */

public class Main {

    static int[] dRow = {0, -1, 0, 1};
    static int[] dCol = {-1, 0, 1, 0};

    static int[][] map = new int[500][500];
    static int[][] dp = new int[500][500]; // dp[i][j] : i,j에서 목표 지점으로 가는 내리막 경우의 수

    static final int NONE = -1;

    static int M;
    static int N;

    static {

        for (int i = 0; i < 500; i++) {

            Arrays.fill(dp[i], NONE);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {

                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve(0, 0);

        System.out.println(dp[0][0]);
    }

    static int solve(int row, int col) {

        //System.out.println("## row = " + row + ", col = " + col);

        if (row == M - 1 && col == N - 1) {

            return 1;
        }

        // memoization
        if (dp[row][col] > NONE) {

            //System.out.println("memoization");
            return dp[row][col];
        }

        int temp = 0;
        for (int i = 0; i < 4; i++) {

            int nextRow = row + dRow[i];
            int nextCol = col + dCol[i];

            if (nextRow < 0 || nextRow >= M || nextCol < 0 || nextCol >= N) {

                continue;
            }

            if (map[nextRow][nextCol] < map[row][col]) {

                temp += solve(nextRow, nextCol);
            }
        }

        return dp[row][col] = temp;
    }

    static void printMap() {

        for (int i = 0; i < M; i++) {

            for (int j = 0; j < N; j++) {

                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
}