2017 카카오코드 예선: 보행자 천국

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

프로그래머스

 

등굣길 문제의 업그레이드입니다. 

https://comdoc.tistory.com/entry/%EB%93%B1%EA%B5%A3%EA%B8%B8-%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95

(파이썬) 등굣길 - 동적계획법

 

JAVA

class Solution {
    int MOD = 20170805;

    public int solution(int m, int n, int[][] cityMap) {
        int[][][] paths = new int[m][n][3];
        paths[0][0] = new int[]{1, 0, 0};
        for (var i = 0; i < m; i++) {
            for (var j = 0; j < n; j++) {
                if (cityMap[i][j] == 0) {
                    if (i > 0)
                        paths[i][j][0] += (paths[i - 1][j][0] + paths[i - 1][j][1]) % MOD;
                    if (j > 0)
                        paths[i][j][0] += (paths[i][j - 1][0] + paths[i][j - 1][2]) % MOD;
                } else if (cityMap[i][j] == 1) {
                    paths[i][j] = new int[]{0, 0, 0};
                } else {
                    if (i > 0)
                        paths[i][j][1] += (paths[i - 1][j][0] + paths[i - 1][j][1]) % MOD;
                    if (j > 0)
                        paths[i][j][2] += (paths[i][j - 1][0] + paths[i][j - 1][2]) % MOD;
                }
            }
        }
        return (paths[m - 1][n - 1][0] + paths[m - 1][n - 1][1] + paths[m - 1][n - 1][2]) % MOD;
    }
}