[세모] 프로그래머스 보행자천국 c++ // dp, 경우의수는 dp를 의심하라.

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

프로그래머스

1. 의사코드 (별:내위치)

4가지 경우의 수가 나온다.

이전 map의 상황에 따라 조건문을 분기한다

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int MOD = 20170805;
int d[504][504][2]; //좌표, 0-> 1아래

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    
    fill(&d[0][0][0],&d[0][0][0]+504*504*2,0);
    //dp[0][0]=0;
    ///-> -> -> 초기화
    for(int i=0;i<m;++i)
    {
        if(city_map[i][0]==1) break;
        d[i][0][1]=1;
    }
    for(int j=0;j<n;++j)
    {
        if(city_map[0][j]==1) break;
        d[0][j][0]=1;
    }

    //return 0;

    for(int i=1;i<m;++i){
        for(int j=1;j<n;++j){
            if(city_map[i-1][j]==0){
                d[i][j][1]+=(d[i-1][j][0]+d[i-1][j][1])%MOD;
            }
            if(city_map[i-1][j]==2){
                d[i][j][1]+=(d[i-1][j][1]%MOD);
            }
            if(city_map[i][j-1]==0){
                d[i][j][0]+=(d[i][j-1][0]+d[i][j-1][1])%MOD;
            }
            if(city_map[i][j-1]==2){
                d[i][j][0]+=(d[i][j-1][0]%MOD);
            }
        }
    }
    
    return (d[m-1][n-1][0]+d[m-1][n-1][1])%MOD;
}

 

 

* 25. 5. 10. 2회독

시도1

참고로 시작점은 표지판이아니므로, ->, 아래가 자동 분기됨.

 

정답코드

n,m이 500*500 -> 완탐시 2^25000(각 칸에서 우측, 아래측 분기) -> 불가 -> dp 필요

class Solution {
    
    static long MOD = 20170805;
    static long dp[][][] = new long [504][504][4];
    static int n,m;
    static int cityMap[][] = new int[504][504];
    static boolean vis[][] = new boolean[504][504];
    static int dy[]={0,1}; //우, 아, 좌, 위 
    static int dx[]={1,0}; // 주의 : <-, 위로가는거 안됨!
    
    long dfs(int y , int x , int dir){
        if(y==m-1 && x==n-1){
            return 1;
        }
        long ret = dp[y][x][dir];
        if(ret!=-1) return ret;
        
        ret=0;
        vis[y][x]=true;
        for(int i=0;i<2;++i){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(ny<0 || nx<0 || ny>=m || nx>=n) continue;
            if(vis[ny][nx]) continue;
            if(cityMap[ny][nx]==1) continue;
            
            if(cityMap[y][x]==2){ //cur을 확인할것!
                //왼쪽에서 오던차(->)는 직진만(->)?
                if(dir==0){
                    if(i==0){
                        ret+=dfs(ny,nx,i);
                    }
                    continue;
                }
                
                //위에서 오던차(|)는 아래로만(|)
                if(dir==1){
                    if(i==1){
                        ret+=dfs(ny,nx,i);
                    }
                    continue;
                }
                continue;    
            }
            
            //그외
            ret += dfs(ny,nx,i)%MOD;
            
            
        }
        vis[y][x]=false;
        
        dp[y][x][dir]=ret%MOD;
        return ret%MOD;
    }
    
    public int solution(int _m, int _n, int[][] _cityMap) {
        for(int i=0;i<504;++i){
            for(int j=0;j<504;++j){
                for(int k=0;k<4;++k){
                    dp[i][j][k]=-1;
                }
            }
        }
        n=_n;
        m=_m;
        cityMap=_cityMap;
        
        return (int)(dfs(0,0,0)%MOD) ;
        
        // return (int)(dfs(0,0,0)%MOD + dfs(0,0,1)%MOD);
    }
}