[프로그래머스] 등굣길 자바

문제 (DP)

 

코딩테스트 연습 - 등굣길

 

 

문제 풀이

 

일단 문제 조건에서 헷갈렸던 것은 mxn행렬이 [m][n]이 아니라 [n][m]을 뜻했다.

그리고 오른쪽과 아래쪽으로만 움직이는 조건 이 큰 힌트가 되었다. 

 

1. 첫번째 행으로 갈 수 있는 최단경로 경우의 수는 오른쪽으로 이동하는 경우이므로 모두 1로 매핑한다.

 

 

2. 두번째 행도 마찬가지로 각 행의 자리로 갈 수 있는 최단경로의 개수를 매핑한다.

 

 

3. 표를 채우다 보면 각 자리의 위와 아래의 값을 더하는 것을 알 수 있다. (조건에서 오른쪽/아래로만 움직인다고도 했고,,)

   물웅덩이는 없는 수 취급한다.

 

 

4. 이 때, 매우 큰 수의 입력이 들어올 수도 있다는 것을 감안하여 각 칸에 1,000,000,007를 미리 나누어서 넣어준다.

 

 

소스 코드

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] area = new int[n+1][m+1];
        for(int i = 0; i < puddles.length; i++)
            area[puddles[i][1]][puddles[i][0]] = -1;
        
        for(int i = 1; i <= m; i++){
            if(area[1][i] == -1)
                break;
            area[1][i] = 1;
        }
        
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(area[i][j] == -1)
                    continue;
                if(area[i-1][j] > -1)
                    area[i][j] += area[i-1][j] % 1000000007;
                if(area[i][j-1] > -1)
                    area[i][j] += area[i][j-1] % 1000000007;
            }
        }
        
        return area[n][m] % 1000000007;
    }
}