(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 등굣길

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

코딩테스트 연습 - 등굣길

top down dp를 이용해 풀었습니다.

풀이방법

 동그라미 표시된 지점으로 가는 방법은 1, 2번 방법 뿐입니다. 따라서,

현재 i,j지점으로 올 수 있는 경우의 수 = (i-1,j로 올 수 있는 경우의 수) + (i,j-1로 올 수 있는 경우의수)가 됩니다.

이를 점화식으로 옮겨볼 수 있습니다. 점화식으로 옮긴다면 다음과 같습니다.

d[i][j] = d[i-1][j] + d[i][j-1]

 

갈 수 없는 경우는 3가지입니다. i번째 행 또는 j번째 열이 지정된 범위를 벗어나는 경우, 그리고 puddle이 있는 경우 입니다. 이 경우에는 갈 수 없으므로 0을 반환합니다. 또한 이미 i,j번째 경로가 계산이 되어있다면 재귀를 호출하지 않고 메모이제이션을 이용해 바로 해당 값을 반환해줍니다.

 

마지막으로 계산된 값은 10억7로 mod연산해준 뒤 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll d[101][101],ck[101][101];
ll dp(int n, int m, int i, int j){
    if(i < 0 || j < 0 || ck[i][j]) return 0;
    if(!i&&!j) return 1;
    ll &ret = d[i][j];
    if(ret!=-1) return ret;
    ret = dp(n,m,i-1,j) + dp(n,m,i,j-1);
    return ret % 1000000007;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    memset(d,-1,sizeof(d));
    memset(ck,0,sizeof(ck));
    for(auto p : puddles) ck[p[1]-1][p[0]-1] = 1;
    return  dp(n,m,n-1,m-1);
}