[lv.3] 등굣길

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

• 문제
  

• 풀이
  해당 칸 수에 올 수 있는 루트를 계산하면 된다.
  
  즉, 집을 1개라고 했을 때, 위쪽, 왼쪽에서 올 수 있는 루트를 합치면서 맨 마지막 학교까지의 루트의 합을 구하면 된다.
  이때, 웅덩이일 경우엔 합하지 않는다.
  식을 정리하면 이렇게 정리할 수 있다.
  dp[i][j] += dp[i-1][j] + dp[i][j-1];
  위의 경우에서 dp[i][j]가 웅덩이, -1이면 위 식을 수행하지 않고, dp[i-1][i]나 dp[i][j-1]이 -1이면 합하지 않는다.

• 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        int[][] dp = new int[m+1][n+1];
        for(int i=0; i<puddles.length; i++){
            dp[puddles[i][0]][puddles[i][1]] = -1;
        }
        dp[1][1] = 1;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(dp[i][j]==-1) continue;
                if(dp[i-1][j]>0) dp[i][j] += dp[i-1][j]%mod;
                if(dp[i][j-1]>0) dp[i][j] += dp[i][j-1]%mod;
            }
        }
        return dp[m][n]%mod; 
    }
}