백준 1520 내리막 길 java

문제

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

1520번: 내리막 길

 

코드

import java.util.*;

public class Main {
    static int n, m;
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, 1, 0, -1 };
    static int[][] arr = new int[500][500];
    static int[][] dp = new int[500][500];

    public static int go(int y, int x) {
        //기저사례
        if(y == m - 1 && x == n -1)
            return 1;

        //메모이제이션
        if(dp[y][x] != -1)
            return dp[y][x];

        //로직
        dp[y][x] = 0;
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || ny >= m || nx < 0 || nx >= n) 
                continue;
            
            if(arr[ny][nx] >= arr[y][x])
                continue;
            
            dp[y][x] += go(ny, nx);
        }

        return dp[y][x];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
 
        arr = new int[m][n];
        dp = new int[m][n];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }

        System.out.println(go(0,0));
    }
}

dp[y][x] = (y,x) 지점일 때 존재하는 경로의 갯수를 저장하여 풀면된다.

전형적인 DFS + DP 문제이다.