99클럽 코테 스터디 40일차 TIL [DP]

- 오늘의 학습 키워드 : dp

[문제 이름 : 등굣길 (프로그래머스 42898, Lv 3)]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/42898

내가 작성한 코드는 아래와 같다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        dp[0][0] = 1;
        
        // 물에 잠긴 지역 -1 설정
        for(int[] puddle : puddles) {
            dp[puddle[1] - 1][puddle[0] - 1] = -1;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                // 물에 잠긴 지역인 경우
                if(dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                }
                
                // 위쪽에서 값 더함
                if(i > 0) {
                    dp[i][j] += dp[i-1][j];
                }
                
                // 왼쪽에서 값 더함
                if(j > 0) {
                    dp[i][j] += dp[i][j-1];
                }
                
                dp[i][j] %= 1000000007;
            }
        }
        
        return dp[n-1][m-1];
    }
}

 

[풀이 과정]

1. 처음 출발할 때를 1로 초기화해주고, puddles에서 물에 잠긴 지역의 x,y좌표를 알 수 있으므로 해당하는 지점을 -1로 초기화 해준다.

2. 오른쪽, 아래 방향으로만 갈 수 있으므로, 이를 다시 생각해보면 왼쪽, 위쪽 값에서 더해질 때만 해당 x,y좌표의 값으로 갱신해주면 된다.

3. dp[i][j]는 (i, j) 위치까지 도달할 수 있는 경로의 수를 저장한다.

4. 문제가 (1,1)에서 시작하므로, dp[n-1][m-1]로 리턴해주었다.

 

풀이 시간 : 35분