프로그래머스 DP - 등굣길

동적계획법 등굣길 문제

 

 

코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp = new int[m+1][n+1];
        for (int[] puddle : puddles) {
            dp[puddle[0]][puddle[1]] = -1;
        }


        dp[1][0] = 1;
        for (int i = 1; i <= m; i++) {

            for (int j = 1; j <= n; j++) {
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % 1000000007;
                }
            }
        }
        answer = dp[m][n];
        return answer;
    }
}

코드 내용 요약

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

물웅덩이의 위치를 -1로 셋팅 그 외에는 0으로 셋팅(자바에서는 초기화와 동시에 배열값이 0으로 셋팅 된다.)

 

dp[1][0]

집의 시작지점은 1가지 길이기 때문에 1로 셋팅

 

 for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % 1000000007;
                }
            }
}

물웅덩이로 가는길 (dp[i][j] == -1) 은 갈 수 있는 길이 0가지 이므로 0으로 재 셋팅

그 외에는 해당 위치의 위와 왼쪽의 갈 수 있는 길의 갯 수 합이 해당 지점으로 가는 길의 갯수가 되므로 더함

문제에서 1000000007로 나눈 나머지 값을 저장 하라고 했으니 % 1000000007로 계산

dp[m][n]이 최종 목적지 까지 가는 길의 갯 수가 됨.