2017 카카오 코드 예선 - 보행자 천국-

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

#include <vector>
#include <cstring>
 
using namespace std;
 
int MOD = 20170805;
int cache[500][500];
 
int move(int m, int n, int y, int x, vector<vector<int>>& city_map) {
    
    if(x > n-1 || y > m-1) return 0;
    if(city_map[y][x] == 1) return 0;
    if(x == n-1 && y == m-1) return 1;
    
    int &ret = cache[y][x];
    if(ret != -1) return ret;
    
    ret = 0;
    
    //아래로 가는 경우
    if(y+1 <= m-1) {
        if(city_map[y+1][x] == 2) {
            int count = 0;
            for(int i = 1; i < m; i++) {
                if(y+1+i < m && city_map[y+1+i][x] == 2) count++;
                else break;
            }
            ret += move(m, n, y + 2 + count, x, city_map) % MOD;
        }
        else ret += move(m, n, y + 1, x, city_map) % MOD;
    }
    else if(y == m-1){
        ret += 0;
    }
       
    
    //오른쪽으로 가는 경우
    if(x+1 <= n-1) {
        if(city_map[y][x+1] == 2) {
            int count = 0;
            for(int i = 1; i < n; i++) {
                if(x+1+i < n && city_map[y][x+1+i] == 2) count++;
                else break;
            }
            ret += move(m, n, y, x + 2 + count, city_map) % MOD;
        }
        else ret += move(m, n, y, x + 1, city_map) % MOD;
    }
    else if(x == n-1){
        ret += 0;
    }
    return ret = ret%MOD;
}
 
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    
    memset(cache, -1, sizeof(cache));
    
    answer = move(m, n, 0, 0, city_map);
    
    return answer;
}

생각을 하지 않고 바로 코딩에 들어갔더니, 너무 복잡한 코드로 구현하였다. 

다음에는 먼저 어떻게 구현할지 손으로 써보고 그다음에 코드로 옮겨야겠다.

 

이번 코딩을 하면서 배운점은, 각각의 경우를 정확히 분류하여 구현했어야 하는데

깊은 생각을 하지 않고 짜는 바람에 많이 꼬여버렸다.

 

다시 공부하면서 위코드에 대해 정리하고 다시 써봐야겠다.