프로그래머스 등굣길

프로그래머스 등굣길 바로가기

문제 설명

집에서 학교 가는데 갈 수 있는 방법의 가짓 수를 구하여라.
근데 물 웅덩이는 지나갈 수 없다!! 이거를 고려해서 가짓수를 구해보자

접근 방식

DP를 이용해서 풀었습니다. 왼쪽과 위쪽의 합을 더해주는 식으로 단순하게 풀었다

코드

import java.util.*;
class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;

        int[][] dp = new int[n+1][m+1];

        for(int[] puddle : puddles){
            dp[puddle[1]][puddle[0]] = -1;
        }

        for(int i = 1; i < m + 1; i++){
            if(dp[1][i] == -1) break;
            dp[1][i] = 1;
        }
        for(int i = 1; i < n + 1; i++){
            if(dp[i][1] == -1) break;
            dp[i][1] = 1;
        }

        for(int i = 2; i < n + 1; i++){
            for(int j = 2; j < m + 1; j++){
                if(dp[i][j] == -1) continue;

                dp[i][j] = ((dp[i-1][j] == -1 ? 0 : dp[i-1][j]) + (dp[i][j-1] == -1 ? 0 : dp[i][j-1])) % 1000000007;

            }
        }
        answer = dp[n][m];

        return answer;
    }
}

Disscussion

이런 디피만 나오면 을매나 좋을까요~~