프로그래머스 level 3 -보행자천국(진행중)

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

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

 

시간초과가 난다. 테스트케이스는 몇개 넣어봣을때 잘 진행되는거보면 일단 논리적인 부분은 틀린것 같진않다.

일단 좀더 고민해봐야할듯하다.

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

int MOD = 20170805;
void Print( vector<vector<int>> city_map){
      for(int i=0;i<city_map.size();i++){
        for(int j=0;j<city_map[i].size();j++){
            
            
            
            cout<<city_map[i][j];
        
        
        }
        
        
        cout<<endl;
    }
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int Func1(int n, vector<vector<int>> city_map, vector<vector<bool>> bCheck,int i,int j){
  // cout<<endl;
    
   // cout<<"i"<<i<<",";
   //  cout<<"j"<<j<<",";
   // cout<<i-n<<",";
    if(i-n<0){
        return 0;
    }
    
    if(bCheck[i-n][j]==true){
       return Func1(n+1, city_map,bCheck,i,j)%MOD;
    }else{
       if(i-n>=0){    
           city_map[i][j]+=city_map[i-n][j]%MOD;
           return  city_map[i][j];
           }else{
           return 0;
       }
    
    }

    
}
int Func2(int n, vector<vector<int>> city_map, vector<vector<bool>> bCheck,int i,int j){
    if(j-n<0){
        return 0;
    }
    
    if(bCheck[i][j-n]==true){
       return Func2(n+1, city_map,bCheck,i,j)%MOD;
    }else{
       if(j-n>=0){    
           city_map[i][j]+=city_map[i][j-n]%MOD;
           return  city_map[i][j];
           }else{
           return 0;
       }
    
    }

    
}
int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    vector<bool>tmpbCheck(n,false);
     vector<vector<bool>> bCheck(m,tmpbCheck);
  
 //   Print(city_map);
    for(int i=0;i<city_map.size();i++){
        for(int j=0;j<city_map[i].size();j++){
        if(city_map[i][j]==1){
            city_map[i][j]=-1;    
        }
        if(city_map[i][j]==2){
            city_map[i][j]=0;
            bCheck[i][j]=true;
        }    
        }
    }
    
      city_map[0][0]=1;
     city_map[m-1][n-1]=0;
    
    for(int i=0;i<city_map.size();i++){
        for(int j=0;j<city_map[i].size();j++){
            
            if(city_map[i][j]==-1){
                city_map[i][j]=0;
                continue;
            }
            
      
            
            if(i!=0){
               
                  city_map[i][j]=Func1(1,city_map,bCheck,i,j)%MOD;
                
            }
            
            if(j!=0){
                  city_map[i][j]=Func2(1,city_map,bCheck,i,j)%MOD;
            }
            
          
        
        
        }
        
        
  //      cout<<endl;
    }
//    cout<<endl;
  //  Print(city_map);
    answer= city_map[m-1][n-1]%MOD;
    return answer;
}