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

문제

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

풀이

class Solution {
    int MOD = 20170805;
    int[][] map;
    public int search(int m, int n, int x, int y, char pre){
        int result=0;
        if(x>=m || y>=n || map[x][y]==1)
            return 0;
        if(x==m-1 && y==n-1)
            return 1;
        if(map[x][y]==0){
            result += search(m,n,x+1,y,'t');
            result += search(m,n,x,y+1,'r');
        }else if(map[x][y]==2){
            if(pre=='t')
                result += search(m,n,x+1,y,'t');
            else
                result += search(m,n,x,y+1,'r');
        }
        result = result%MOD;
        return result;
    }
    public int solution(int m, int n, int[][] cityMap) {
        map = cityMap;

        int answer = search(m,n,0,0,'r');
        return answer;
    }
}

테스트 케이스는 통과하였지만 코드 채점에서 계속 시간초과가 뜬다!!!

재귀적으로 풀면 안되는 모양이다......

동적프로그래밍으로 풀어야 하나보다 동적프로그래밍을 공부해야겠다.