[프로그래머스]등굣길 -JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

오른쪽과 아래로만 움직일 수 있는 최단 거리 계산이다.

각 위치에서 왼쪽과 위에서 올 수 있는 경우의 수를 다 더해주면 된다.

class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        
        System.out.println(s.solution(4, 3,new int[][]{{2,2}}));
    }
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 0; i < puddles.length; i++) {
            dp[puddles[i][0] - 1][puddles[i][1] - 1] = -1;
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j ++) {
                if(dp[i][j] == -1) continue;

                if(i > 0 && dp[i - 1][j] != -1) {
                    dp[i][j] += dp[i - 1][j];
                }

                if(j > 0 && dp[i][j - 1] != -1) {
                    dp[i][j] += dp[i][j - 1];
                }

                dp[i][j] %= 1000000007;

            }
            
        }
        



        return dp[m - 1][n - 1];
    }
}