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

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

프로그래머스

 

어릴 때, 확률과 통계에서 풀었던 것처럼 천천히 갈 수 있는 길을 계산해보면 된다.

 

배열을 순차적으로 돌면서 내 위치에서 왼쪽 길과 윗 길을 확인해서 웅덩이가 있다면 큰 값을 선택하고

그렇지 않다면 합친 값을 내 위치에 기록한다.

 

이때 중요한 건 1000000007로 나눠야 한다.

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];
        
        dp[1][1] = 1;
        
        for(int[] puddle : puddles){
            dp[puddle[1]][puddle[0]] = -1;
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(dp[i][j] == -1)
                    continue;
                if(i == 1 && j == 1)
                    continue;
                
                if(dp[i - 1][j] == -1 || dp[i][j - 1] == -1){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] %= 1000000007;
                } else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    dp[i][j] %= 1000000007;
                }
            }
        }
        
        // for(int i = 1; i <= n; i++){
        //     for(int j = 1; j <= m; j++){
        //         System.out.print(dp[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        return dp[n][m];
    }
}