프로그래머스 등굣길

문제

풀이

오른쪽과 아래로만 이동하기 때문에 현재 위치에서 위에서 오는 경우와 왼쪽에서 오는 경우를 더해준다. 대신 웅덩이에서는 0으로 해준다.

---

코드

class Solution {
    static int[][] dp;
    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        dp=new int[n+1][m+1];
        for(int i=0;i<puddles.length;i++){
            dp[puddles[i][1]][puddles[i][0]]=-1;
        }

        dp[1][1]=1;

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

        return answer;
    }
}

#dp