[java] 프로그래머스 : 등굣길

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

프로그래머스

풀이 접근법 : n,m으로 DP 배열(n+1, m+1)을 만들고 웅덩이는 루트 계산에서 빼기 위해 0으로 처리해 경로 계산을 해준다. dp[i][j] += (dp[i-1][j]+dp[i][j-1]) 의 의미는 왼쪽에서 오는 경우와 위쪽에서 오는 경우를 합친 경우의 수이다

 

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
            int answer = 0;
            int[][] dp = new int[n+1][m+1];

            for(int[] puddle : puddles){
                dp[puddle[1]][puddle[0]] = -1;
            }

            dp[1][1] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (dp[i][j] == -1) {
                        dp[i][j] = 0;
                        continue;
                    }
                    dp[i][j] += (dp[i-1][j]+dp[i][j-1]) % 1000000007;
                }
            }


            return dp[n][m];
        }
}