[백준 1520번] 내리막 길

문제 링크: 1520번 제목

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

 

P(i, j)가 (i, j)의 위치에서 출발지까지 가는 경로의 수를 나타낸다고 한다면 이는 다음과 같은 식으로 표현된다.

P(i, j) = sum({P(k, l) | (k, l)은 (i, j)와 인접 & (k, l)은 (i, j)보다 고도가 높음})

P(i, j)의 초기값을 -1로 설정해두어서 방문 여부를 표시한다면, (i, j)를 방문한 경우 P(i, j)를 바로 사용하면 되며 이는 다시 계산할 필요가 없다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int m;
    static int n;
    static int[][] map;
    static int[][] dp;
    static int[] drow = {-1, 0, 1, 0};
    static int[] dcol = {0, 1, 0, -1};

    public static int solution(int row, int col) {
    	// 출발지의 경로 수는 1
        if (row == 1 && col == 1) return 1;
        
        // 이미 계산한 적이 있는 위치이면 저장해둔 값을 사용
        if (dp[row][col] != -1) return dp[row][col];

        int sum = 0;
        for (int d = 0; d < 4; d++) {
            int r = row + drow[d];
            int c = col + dcol[d];

            if (r<0 || c<0 || r>m || c>n) continue;
            if (map[r][c] <= map[row][col]) continue;

            sum += solution(r, c);
        }
        dp[row][col] = sum;
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = bf.readLine().split(" ");
        m = Integer.parseInt(temp[0]);
        n = Integer.parseInt(temp[1]);

        // create map
        map = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            temp = bf.readLine().split(" ");
            for (int j = 1; j <= n; j++)
                map[i][j] = Integer.parseInt(temp[j-1]);
        }

        // create dp
        dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j] = -1;

        System.out.println(solution(m, n));
    }
}