[DP] 보행자 천국(프로그래머스)

https://school.programmers.co.kr/learn/courses/30/lessons/1832?language=java# 

프로그래머스

 

 

1. DP값을 갱신할 때마다 %MOD 해주기 

2. dp[ ][ ][ 0: 오른쪽 / 1: 아래쪽 ]

 

import java.util.*;

 //프로그래머스
public class Solution_보행자천국{

    static int MOD = 20170805;
    static int[] dx={0,1}; //[0]은 오른쪽, [1]: 아래
    static int[] dy={1,0};
    static Queue<int[]> q;
    static int[][][] dp;

    public static void main(String[] args) {
    
    	int m=3; 
    	int n=6;
    	
    	int[][] cityMap= {{3,2,0,0,0,2},{0,0,2,0,1,0},{1,0,0,2,2,0}};
    	int answer=solution(m,n,cityMap);
    	System.out.println(answer);
    
    }
    

    public static int solution(int m, int n, int[][] cityMap) {
        int answer = 0;

        q=new LinkedList<>();
        dp=new int[m][n][2]; 

        for(int i=0;i<n;i++) { 
            if(cityMap[0][i]==1) break;
            dp[0][i][0]=1;
        }

        for(int i=0;i<m;i++) {
            if(cityMap[i][0]==1) break;
            dp[i][0][1]=1;
        }


        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                if(cityMap[i][j]==1) {
                    continue;
                }
                if(cityMap[i-1][j]==2) { //위쪽 값이 2이라면
                    if(dp[i-1][j][1]>0) {
                        dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][1])%MOD;
                    }
                }
                else { //위쪽 값이 2가 아니라면
                    dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][1]+dp[i-1][j][0])%MOD;
                }

                if(cityMap[i][j-1]==2) {//왼쪽 값이 2라면
                    if(dp[i][j-1][0]>0) 
                        dp[i][j][0]=(dp[i][j][0]+dp[i][j-1][0])%MOD;
                }
                else {//왼쪽 값이 2가 아니라면 
                    dp[i][j][0]=(dp[i][j][0]+dp[i][j-1][1]+dp[i][j-1][0])%MOD;
                }

            }
        }

        answer=(dp[m-1][n-1][0]+dp[m-1][n-1][1])%MOD;
       return answer;
        }

}