프로그래머스(등굣길)

첫 시도

• 누적합을 사용하여 해결 가능
• 내가 구할 위치의 값 = [i-1][j]까지의 경우의 수 + [i ][j-1]까지의 경우의 수 이므로 누적합을 이용해서 모든 배열에 값을 넣어주면 된다.
• 시간복잡도는 배열 크기만큼 이므로 O(NM)이다.

해결

class Solution {

        public int solution(int m, int n, int[][] puddles) {
            int mod = 1000000007;

            int[][] board = new int[n + 1][m + 1];
            for (int i = 0; i < puddles.length; i++) {
                board[puddles[i][1]][puddles[i][0]] = -1;
            }

            board[1][1] = 1;
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    if (board[i][j] == -1) continue;
                    if (board[i - 1][j] > 0) board[i][j] += board[i - 1][j] % mod;
                    if (board[i][j - 1] > 0) board[i][j] += board[i][j - 1] % mod;
                }
            }
            return board[n][m] % mod;
        }
}

참고

• https://moonsbeen.tistory.com/75