[Programmers] 보행자 천국

int MOD = 20170805;

int r[501][501]; //i,j위치에서 오른쪽으로 갈 수 있는 경우의 수
int b[501][501]; //i,j 아래쪽으로 갈 수 있는 경우의 수
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(r, 0, sizeof(r));
    memset(b, 0, sizeof(b));
    MOD = 20170805;
    r[1][1] = b[1][1] = 1; //첫 위치에서는 아래쪽이나 오른쪽으로 갈수 있는 한 가지의 경우에서 출발
    
    for(int i=1; i<=m;i++){
        for(int j=1;j<=n;j++){
            if(city_map[i-1][j-1]==0){
                r[i][j] = (r[i][j] + r[i][j-1] + b[i-1][j])%MOD; //0인 경우 왼쪽이나 위쪽에서 오는 경우를 더하면 됨
                b[i][j] = (b[i][j] + r[i][j-1] + b[i-1][j])%MOD; //0인 경우 왼쪽이나 위쪽에서 오는 경우를 더하면 됨
            }
            else if(city_map[i-1][j-1]==1){
                r[i][j] = 0; //1인 경우 막혀서 갈 수가 없음
                b[i][j] = 0; //1인 경우 막혀서 갈 수가 없음
            }
            else{
                r[i][j] = r[i][j-1]; //2인 경우 왼쪽에서 오는 차량만 지나갈 수 있음
                b[i][j] = b[i-1][j]; //2인 경우 왼쪽에서 오는 차량만 지나갈 수 있음
            }
        }
    }
    
    return (r[m][n-1]+b[m-1][n])%MOD; //목적지까지 갈 수 있는 경우의 수는 왼쪽에서 오는 경우와 위쪽에서 오는 경우를 더한 것임
}

int MOD = 20170805;
int solution(int n, int m, vector<vector<int>> city_map) {
    int dp[n+1][m+1][2]; // [][][0] : 가로 / [][][1] : 세로
    memset(dp, 0, sizeof(dp));
    
    dp[1][1][0] = dp[1][1][1] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if( city_map[i-1][j-1] == 0){
                dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][1] + dp[i][j-1][0]) % MOD;
                dp[i][j][1] = (dp[i][j][1] + dp[i-1][j][1] + dp[i][j-1][0]) % MOD;
            }
            else if( city_map[i-1][j-1] == 1){
                dp[i][j][0] = dp[i][j][1] = 0;
            }
            else {
                dp[i][j][0] = dp[i][j-1][0] % MOD;
                dp[i][j][1] = dp[i-1][j][1] % MOD;
            }
        }
    }
    
    return max(dp[n][m][0],dp[n][m][1]);
}