등굣길

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

예제를 아래처럼 엑셀에서 내 나름의 생각대로 

숫자를 적으면서 보니

어떤 한 정점 기준으로 그 정점의 윗 칸과 왼쪽 칸을 더하였더니

아래처럼 나왔고, (n, m)=(행, 열)=(3, 4)의 칸의 숫자가 4여서

혹시나해서 구현해서 제출하였고

한 번에 맞았다.

솔직히 틀릴 줄 알았다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Mod 1000000007
 
int Map[111][111] = { 0, }, dp[111][111] = { 0, };
 
int solution(int m, int n, vector<vector<int>> puddles)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            Map[i][j] = 1;
 
    for (auto i : puddles)
        Map[i.at(1)][i.at(0)] = 0;
    
    dp[1][1] = 1;
 
    for (int i = 1; i <= n; i++)    
        for (int j = 1; j <= m; j++)
        {
            if (!Map[i][j]) continue;
            dp[i][j] = dp[i][j] % Mod + dp[i - 1][j] % Mod + dp[i][j - 1] % Mod;        
        }
    
    return dp[n][m] % Mod;
}
 
int main(void)
{
    vector<vector<int> > v = { {2, 2} };
 
    cout << solution(4, 3, v) << '\n';
 
    return 0;
}