프로그래머스 - 등굣길 문제 (자바)

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

코딩테스트 연습 - 등굣길

집의 dp값을 1로 두고 

웅덩이가 아닌 경우 왼쪽과 윗쪽의 값을 합친 값으로 본인 dp를 설정

웅덩이인 경우 dp를 0으로 둠

 

주의점

1. 리턴해야하는 게 1000000007으로 나눈 나머지를 해야하는데 효율성 부분에서 이 숫자를 dp를 구하는 과정에서 넘어감 -> dp 구하는 과정에서 나눈 나머지를 셋팅

2. dp를 구할 때 map의 영역을 벗어난 경우 0으로 하기 위해서 map의 크기를 가로 세로 +1씩 함

// 프로그래머스 등굣길 문제
class GoToSchool {

    static final int MOD = 1000000007;

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

        // 웅덩이를 map에 표시
        for (int[] puddle : puddles) {
            map[puddle[1]][puddle[0]] = 1;
        }
        // 집 dp 초기화
        dp[1][1] = 1;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                // 집위치는 위에서 초기화 해서 넘어감
                if(i== 1 && j == 1) continue;
                // 웅덩이의 경우 넘어감 - 해당위치 dp 값은 0
                if(map[i][j] == 1) continue;
                // 위, 아래 dp의 합으로 셋팅
                dp[i][j] = dp[i-1][j] % MOD + dp[i][j-1] % MOD;
            }
        }
        return dp[n][m] % MOD;
    }
}