Gidhub BE Developer

Programmers - 보행자 천국

2018-08-01
goodGid

Problem

Problem URL : 보행자 천국


[1] Answer Code (18. 08. 01)


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; //목적지까지 갈 수 있는 경우의 수는 왼쪽에서 오는 경우와 위쪽에서 오는 경우를 더한 것임
}



[2] Answer Code (18. 08. 01)


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]);
}



[1],[2] Answer Code (18. 08. 01)

정답코드를 보고 이해하는데 2일 걸렸다.

우선 city_map[i-1][j-1]과 r[i][j],b[i][j]의 관계에 대해 이해가 안됐다.

i,j를 1부터 시작하기 때문에

city_map의 인덱스는 i-1,j-1로 실제로 원하는 좌표값을 잡아주는 것이였다.

만약 i,j를 0부터 시작한다면 city_map의 인덱스는 i,j처럼 이쁘게 나오겠지만

r[i][j-1]과 같은 로직을 처리하기위해 if문이 추가되어야한다.

즉 city_map[i-1][j-1]은 r[i][j],b[i][j]와 같은 좌표값을 가리키는 것이였다.


오랜만에 DP를 접근하니까 너무 헷갈리고 머릿속에서 정리가 안되었다.

이 문제 덕분에 DP에 대해 다시금 피드백을 할 수 있었다. 굿 !


Comments

Content