오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지 구하는 문제

→ 2차원 배열에 오른쪽&아래쪽 즉 우측 대각선을 내려가는 방향으로 갈 수 있는 경우의 누적합

아래 그림을 살펴보면 오른쪽과 아래쪽의 방향으로 2차원 배열의 요소를 더해주면서 가능한 경로의 누적합을 구한다. ※ 문제의 index가 헷갈리니 주의!

<aside> ❓ 요소의 값 board[i][j] = board[i-1][j] + board[i][j-1] → (아래쪽 방향 + 오른쪽 방향)

</aside>

이때 다음 로직을 추가해주면 정답!

• index의 범위가 넘어가는 것을 방지하기 위해 0번째 행과 0번째 열의 값을 0으로 저장
• puddle에 해당하는 index의 요소는 0으로 저장

풀이 코드

※ 이때 모듈러 연산을 하지 않는다면 효율성 테스트가 다 틀린다. board에 넣어 주는 경우와 정답을 반환하는 경우 모두 모듈러 연산을 해주어야 한다!

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int limit_mod = 1000000007;
        
        int[][] board = new int[n+1][m+1];
        
        //puddles을 -1로 표시
        for(int i=0; i<puddles.length; i++) {
            board[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        //(1,1)을 1로 초기화
        board[1][1] = 1;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(i==1 && j==1) continue;
                if(board[i][j] == -1)
                    board[i][j] = 0;
                else
                    board[i][j] = (board[i-1][j] + board[i][j-1]) % limit_mod;
            }
        }
        
        answer = board[n][m];
        
        return answer % limit_mod;
    }
}