[프로그래머스/DP] Level 3 등굣길 (JAVA)

문제

---

풀이

오른쪽 아래로만 이동이 가능한데, 사실 그렇게만 이동하면 결국 최단 거리를 보장한다.
그렇기 때문에 점화식은 dp[i][j] = dp[i-1][[j] + dp[i][j-1]으로 간단하게 생각해낼 수 있다.

dp 배열을 static으로 최대 사이즈보다 1 크게 선언해놓으면 굳이 0으로 padding 처리를 해줄 필요 없이 자동으로 0으로 채워진다. 그래서 isPuddle() 여부를 인덱스와 puddles 배열을 통해 확인하고, 이에 대해 0 처리만 해주면 정답을 얻을 수 있다.

코드

class Solution {
    
    private static final int MOD = 1000000007;
    private static final int MAX = 100;
    private static final int X = 0;
    private static final int Y = 1;
    
    private int[][] dp = new int[MAX + 1][MAX + 1];

    public int solution(int m, int n, int[][] puddles) {
        dp[0][1] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (isPuddle(i, j, puddles)) dp[i][j] = 0;
                else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        return dp[n][m];
    }

    private boolean isPuddle(int i, int j, int[][] puddles) {
        for (int[] puddle : puddles)
            if (puddle[Y] == i && puddle[X] == j) return true;

        return false;
    }
}