[2017 카카오 예선] 보행자 천국

2017 카카오코드 예선

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

 

코딩테스트 연습 - 보행자 천국 | 프로그래머스

 

컨셉

고등학교 때 했던 수학문제. 간 단 쓰.

 

 

way[i][j] //(i,j)까지 갈 수 있는 방법의 수

way[i][j] = way[i-1][j] + way[i][j-1] //위에서 오는 방법의 수 + 왼쪽에서 오는 방법의 수

 

단, 직진코스(city_map 값이 2인 경우)이 있는 경우는 조금 다르다.

- 직진인 경우: 해당 방향으로 직진이 아닌 길이 나올때까지 더 진행해서 더함.

 

예제 2번)

 빨간글씨: way[i][j].

ex) way[1][5] = way[0][1] (위에서 오는 방법) + way[1][4] (왼쪽에서 오는 방법)

ex) way[2][5] = way[1][5] (위에서 오는 방법) + way[2][2] (왼쪽에서 오는 방법. 직진코스를 만났기 때문에 [2][2]까지 밀려남)

 

 

 

초안

내가 쓴 코드(27.25ms, 6.46MB, 정답)

 

/**
 * 보행자 천국
 * https://programmers.co.kr/learn/courses/30/lessons/1832
 * 2019-09-03 by Sunmon
 * 
*/
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
 
int way[500][500];  //way[i][j]: city_map[i][j]로 갈 수 있는 경우의 수
int MOD = 20170805;
 
//city_map[i][j]까지 갈 수 있는 방법의 수를 리턴한다.
int finding(int i, int j, vector<vector<int>>& city_map)
{
    //base case
    if(i < 0 || j < 0) return 0;
 
    //이미 경우의 수를 아는 경우 리턴    
    int& ret = way[i][j];
    if(ret!= -1) return ret;
    if(city_map[i][j] == 1) return ret = 0;
    
    ret = 0;
    
    //위와 왼쪽에서 오는 방법의 수
    int FROM_UP = 0, FROM_LEFT = 0;
    for(int k = 1; k<=j; k++)
    {
        if(city_map[i][j-k] == 2) continue;
        FROM_LEFT = finding(i, j-k, city_map);
        break;
    }
    for(int k = 1; k<=i; k++)
    {
        if(city_map[i-k][j] == 2) continue;
        FROM_UP = finding(i-k, j, city_map);
        break;
    }
 
    ret = (ret + FROM_UP) % MOD;
    ret = (ret + FROM_LEFT) % MOD;
    return  ret;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(way, -1, sizeof(way));
    way[0][0] = 1;
    int answer = finding(m-1, n-1, city_map);
    return answer;
}

 

주의

MOD 잊지말자