[프로그래머스] 등굣길 c++

풀이

(1,1)에서 (m,n)까지 가는 최단 경로의 개수를 구해야한다. 중간에 물웅덩이를 지날 수 없다.

m이 x축이고 n이 y축이다.  puddles도 (x축 좌표, y축 좌표)이다. 예시로 준 물웅덩이가 2,2라 헷갈릴 수 있다.

1. 물웅덩이의 값을-1로 설정한다. 
2. i,j까지 오는 경우의 수는 (i-1,j)와 (i,j-1)에서 오는 경우의 수뿐이다 (오른쪽과 아래쪽으로 밖에 못 움직인다.)
3.두 방향에 각각 물웅덩이가 있는지 검사하고 없다면 경우의 수를 더한다.
4.물웅덩이는 지나갈 수 없으므로 더하지 않고 continue해준다. 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>>dp(101,vector<int>(101,0));


int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    for(auto p :puddles){
        dp[p[1]][p[0]] = -1;
    }
    dp[1][1]=1;
    for(int i= 1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dp[i][j]<0)
                continue;
           if(dp[i][j-1]>0)
               dp[i][j]+=dp[i][j-1];
            if(dp[i-1][j]>0)
                dp[i][j]+=dp[i-1][j];
            dp[i][j]%=1000000007;
            
        }
    }
    answer= dp[n][m];

    return answer;
}