[프로그래머스 알고리즘] 등굣길 (Level 3)

문제

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

풀이

DP문제이다. 어차피 오른쪽과 아래로만 움직이면 무조건 최단경로이기 때문에 이 부분은 신경쓰지 않아도 된다. (1, 1)을 1로 초기화 하고, 각 지점에서 위와 왼쪽의 경로 수를 더해주면 된다. 예를 들면,

동그라미 친 부분까지 가는 경로의 수는 위와 왼쪽을 더하여 2가 된다. 각 지점을 모두 이렇게 구하여 (1, 1)부터 시작해서 (n, m)까지 진행하면 된다. 웅덩이는 -1로 초기화하여 경우의 수에서 고려하지 않도록 하였다.

코드

import java.util.*;
//현재 위치의 왼쪽, 위쪽 탐색하면서 가짓수 더하기 
class Solution {
//    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int num = 1000000007;
        int[][] dt = new int[n + 1][m + 1]; 
//
        dt[1][1] = 1;
//       
        for(int i = 0; i < puddles.length; i++) {
            dt[puddles[i][1]][puddles[i][0]] = -1; 
        }
//        
        for(int i = 1; i <= n; i++){        //y좌표
            for(int j = 1; j <= m; j++){     //x좌표
//
                if(dt[i][j] == -1) continue;
//             
                if(dt[i - 1][j] > 0){     //위쪽이 범위 밖이거나 물웅덩이가 아니면
                    dt[i][j] += dt[i - 1][j] % num;      //위쪽의 값 더함
                }
                if(dt[i][j - 1] > 0){       //왼쪽이 범위 밖이거나 물웅덩이가 아니면
                    dt[i][j] += dt[i][j - 1] % num;      //왼쪽의 값 더함
                }
//                
            }
        }
//        
        answer = dt[n][m] % num;	
//                
        return answer;
    }
}

answer = dt[n][m] % num; 이유

매번 num으로 나눈 나머지를 더했는데 마지막에 % num을 해주어야 하는 이유는 ?
-> 예를 들어, num이 100이라 가정하고 40 % 100 과 90 % 100을 더했으면 dt[n][m]은 40 + 90으로 130이 된다. 따라서, 이를 한번 더 100으로 나눠주어야 원하는 값이 나온다.