안녕하세요 카카오 코드페스티벌 나갔다가 2문제 풒고 광탈한 코알못입니다..

2번 문제를 dp로 풀다가 계속 실패해서 다른 문제를 풀었는데 시간이 끝나고 다시 풀어봐도 잘 모르겠습니다.

카카오에서 설명해주는 방식말고 3차원 dp(원래 풀던 방식)으로 풀고싶은데 .. 쉽지않습니다..ㅠ

문제 링크

http://tech.kakao.com/2017/08/...

코딩 고수님들 좀 도와주세요 ㅠㅠ

제가 작성한 코드는 아래와 같습니다.

#include <vector>
#include <cstring>
using namespace std;

typedef enum DIR {LEFT, DOWN}; // 위에서 내려왔는지 왼쪽에서 왔는지

int MOD = 20170805;
int dp[500][500][2]; // dp 배열 [m][n][0] = 왼쪽에서 오는 경우, [m][n][1] = 위에서 오는 경우
int mx, my; // 배열의 범위

int rec(int m, int n, int dir, vector<vector<int>> &map) {
    
    if(m < 0 || n < 0 || mx <= m || my <= n) return 0;  // 범위를 벗어나면 return 0
    if(m == mx - 1 && n == my - 1) return 1; // 도착하면 return 1
    
    int &ret = dp[m][n][dir]; // 
    
    if(ret != -1) return ret; // 이미 온 경우
    
    ret = 0;
    
    if(map[m][n] == 0) 
        ret += (rec(m+1,n,DOWN,map) % MOD) + (rec(m,n+1,LEFT,map) % MOD); // 좌표값이 0인 경우 오른쪽, 아래 재귀
    
    else if(map[m][n] == 1) return 0; // 막혀있으면 return 0
    
    else { // 좌표값이 2인 경우
        
        if(dir == DONW) ret += (rec(m+1,n,DOWN,map) % MOD); // 위에서 내려온 경우엔 아래로만 
        else ret += (rec(m,n+1,LEFT,map) % MOD); // 왼쪽에서 온 경우엔 오른쪽으로만
    }
    
    return ret;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    mx = m; my = n;
    memset(dp,-1,sizeof(dp));

    answer = rec(0,0,DOWN,city_map); // dp 시작
    return answer;
}

과연 어디가 틀린걸까요 ㅠㅠ...