[C++]등굣길

요약

• Bottom-Top 방식의 DP 적용

풀이과정

1. DP 배열 셋팅하기

표시를 쉽게 하기 위해 index 0은 사용하지 않고, 크기가 n+1,m+1인 배열을 선언한다.

그리고 0으로 초기화한다음, (1,1) 값만 1로 초기화한다.

    int DP[n+1][m+1];
    memset(DP,0,sizeof(DP));
    DP[1][1] = 1;

2. 점화식 짜기

굉장히 직관적으로,

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

이라는 것을 알 수 있다. 물론 i,j의 범위를 고려해줘야 함.

3. puddle과 

예제의 경우

0	0	0	0	0
0	1(집)	0	0	0
0	0	0	0	0
0	0	0	0	학교

이러한 상황인데, 만약, DP[i][j]가 puddle이라면 무조건 0으로 한다.

그렇게 하면, 나중에 점화식의 항으로 puddle이 들어가도, 0이 더해지기 때문에 따로 처리를 할 필요가 없다.

puddle 찾기는 algorithm의 find를 사용하였다.

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            vector<int> p = {j,i};
            auto check = find(puddles.begin(), puddles.end(), p);
            if(check != puddles.end())  //puddle
                DP[i][j] = 0;
            else if(i != 1 || j != 1)
                DP[i][j] = (DP[i-1][j]+DP[i][j-1]) % DIV;
        }
    }

가장자리 부분도 둘러싼 부분이 모두 0으로 초기화되어있기 때문에 따로 if 범위를 나누지 않아도 된다.

코드

#include <bits/stdc++.h>
using namespace std;

#define DIV 1000000007


int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int DP[n+1][m+1];
    memset(DP,0,sizeof(DP));
    DP[1][1] = 1;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            vector<int> p = {j,i};
            auto check = find(puddles.begin(), puddles.end(), p);
            if(check != puddles.end())  //puddle
                DP[i][j] = 0;
            else if(i != 1 || j != 1)
                DP[i][j] = (DP[i-1][j]+DP[i][j-1]) % DIV;
        }
    }
    
    // for(int i = 1; i <= n; i++)
    // {
    //  for(int j = 1; j <= m; j++)
    //     cout<<DP[i][j] << " ";
    //  cout << endl;
    // }

    answer = DP[n][m];
    return answer;
}