프로그래머스 - 보행자 천국

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

코딩테스트 연습 - 보행자 천국

1. 유형

DP

 

2. 시뮬레이션

로직

1. 맵을 완전탐색 한다.
2. 현재의 칸에서 상, 좌를 확인한다
   1. 이전 칸이 0 OR 2에 따라 분기한다. 위의 그림의 공식대로 Dp에 저장
3. 위를 n-1,m-1 좌표까지 반복

3. 코드

class Solution {
    int MOD = 20170805;
    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        int dp[][][] = new int[2][m][n];
        int dir[][] = {{-1,0}, {0,-1}};//상, 좌
        dp[0][0][0] = 1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(cityMap[i][j] == 1) continue;
                for(int k=0; k<2; k++){
                    int pr = i+dir[k][0];
                    int pc = j+dir[k][1];
                    if(pr<0 || pc<0 ) continue;
                    if(cityMap[pr][pc] == 2){
                        dp[k][i][j] += (dp[k][pr][pc]%MOD);
                    }else{
                        dp[k][i][j] += ((dp[0][pr][pc]+dp[1][pr][pc])%MOD);
                    }
                }
            }
        }
        answer = dp[0][m-1][n-1] + dp[1][m-1][n-1];                                                 
        return answer%MOD;
    }
}