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

🔗 문제링크

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

👩🏻‍💻 코드

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

        for (int i = 0; i < puddles.length; i++) {  // 웅덩이 표시
            dp[puddles[i][1]][puddles[i][0]] = -1;
        }

        // 왼쪽, 위쪽에 웅덩이 있으면 경우의 수 증가 X
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= m; col++) {
                if (row == 1 && col == 1) {
                    dp[1][1] = 1;
                    continue;
                }

                if (dp[row][col] == -1) {
                    continue;
                }

                int top = dp[row - 1][col];
                int left = dp[row][col - 1];
                if (dp[row - 1][col] == -1) {
                    top = 0;
                }
                if (dp[row][col - 1] == -1) {
                    left = 0;
                }
                dp[row][col] = (top + left) % 1000000007;
            }
        }

        return dp[n][m];
    }
}

📝 정리

dp 배열을 통해 웅덩이가 있으면 표시해 주고, 마지막 칸까지 top과 left를 더해가며 계산해 주었다.
return 할 때만 1000000007로 모듈러 연산을 해주면 되는 줄 알았는데 dp에 저장할 때마다 해줬어야 했다.