[pro] 프로그래머스 level3 42898 등굣길 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

웅덩이가 있다면 그 길을 통해서 올 수 없으므로 계산을 하지 않는다.

위 경우를 제외하고는 좌표에서 벗어나지 않는 범위에서, 위에서 오는 경우의 수와 왼쪽에서 오는 경우의 수를 dp 배열에 더해줌으로써 계산 가능하다. 

 

[코드]

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        // 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 
        //n, m. dp[i][j]
        int[][] dp = new int[n+1][m+1];
        int[][] map = new int[n+1][m+1];
        
        for(int[] p:puddles){
            int x = p[0];
            int y = p[1];
            map[y][x] = -1; //웅덩이
        }
        
        dp[1][1] = 1;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(map[i][j]==-1){
                    continue;
                }
                if(i>1){
                    dp[i][j] += dp[i-1][j]%1000000007;
                }
                if(j>1){
                    dp[i][j] += dp[i][j-1]%1000000007;
                }
            }
        }
        
        answer = dp[n][m]%1000000007;
        
        return answer;
    }
}