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

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

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

 

이런류의 문제는 dp로 n^2 풀이가 가능하다

다만 차의 방향상태를 나눠서 저장해준다.

 

dp[i][j][0] = i,j에서 차가 오른쪽으로 갈 수있는 경우의 수

dp[i][j][1]= i,j에서 차가 아래로 갈 수있는 경우의 수

 

그 후

city_map이 0이냐 1이냐에 따라 다르게 처리를 해준다.

 

0인 경우 :

현위치에서 위에서 오는 경우의 수 왼쪽에서 오는 경우의 수의 합이

현위치에서 오른쪽, 아래 둘 다 갈 수 있으므로 dp[i][j][0] 과 dp[i][j][1] 둘 다 추가해준다.

 

1인 경우 :

위에서 오는 경우는 아래로 가는 경우에만 (dp[i][j][1]에만) 추가

왼쪽에서 오는 경우는 오른쪽으로 가는 경우에만 추가 (dp[i][j][0]에만) 추가.

 

도착점은 map이 0이기떄문에 dp[m-1][n-1][0] 과 dp[m-1][n-1][1] 중 아무거나 출력해주면 된다.

 

#include <vector>
#include <memory.h>
#include <iostream>
using namespace std;
 
int MOD = 20170805;
int dp[501][501][2];  // 0 오른쪽 1 아래
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1; 
    dp[0][0][1]=1;
    for(int i=1;i<n;i++){
        if(city_map[0][i]==0){
            dp[0][i][0]=dp[0][i-1][0];
            dp[0][i][1]=dp[0][i-1][0];
        }
        else if(city_map[0][i]==2){
            dp[0][i][0]=dp[0][i-1][0];
        }
    }
    for(int i=1;i<m;i++){
        if(city_map[i][0]==0){
            dp[i][0][1]=dp[i-1][0][1];
            dp[i][0][0]=dp[i-1][0][1];
        }
        else if(city_map[i][0]==2){
            dp[i][0][1]=dp[i-1][0][1];
        }
    }
    
    
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if(city_map[i][j]==0){
                dp[i][j][0]+=(dp[i][j-1][0]+dp[i-1][j][1])%MOD;
                dp[i][j][1]+=(dp[i][j-1][0]+dp[i-1][j][1])%MOD;
            }
            else if(city_map[i][j]==2){
                dp[i][j][0]+=dp[i][j-1][0]%MOD;
                dp[i][j][1]+=dp[i-1][j][1]%MOD;
            }
            dp[i][j][0]=dp[i][j][0]%MOD;
            dp[i][j][1]=dp[i][j][1]%MOD;
        }
    }
 
    answer=dp[m-1][n-1][0]%MOD;
    
    return answer;
}