[프로그래머스] [C++] 등굣길 (dp)

1. 문제

 

코딩테스트 연습 - 등굣길 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 등굣길

 

2. 풀이

배열 m*n을 만든다음 

해당 상태에

방문안했으면 -1

방문했으면  이전 값 리턴 하는 식으로 작동한다.

이 때 우물을 전부 방문했다고 가정하여 0으로 두면 자연스럽게 결과값이 나온다.

 

#include <vector>
#include <cstring>
 
using namespace std;
 
const int div = 1000000007;
 
int cached[102][102];
int dp(vector<vector<int> >& puddles, int m, int n, int i, int j) {
    int& ret = cached[i][j];
    
    if(i == m && j == n)
        return 1;
    if(i > m || j > n)
        return 0;
    if(ret != -1)
        return ret;
    
    return ret = (dp(puddles, m, n, i, j + 1) + dp(puddles, m, n, i + 1, j))%div;
}
 
int solution(int m, int n, vector<vector<int>> puddles) {
    memset(cached, -1, sizeof cached);
    for(int i = 0; i < puddles.size(); i++)
        cached[puddles[i][0]][puddles[i][1]] = 0;                        
    return dp(puddles, m, n, 1, 1); 
}