4. 등굣길

    4번 문제   

 

---

    내가 풀이한 답   

 

 장애물이 없는 경우와 장애물이 있는 경우를 살펴보면 장애물이 없을 때 (1, 1)에서 (3, 3)까지 갈 수 있는 방법은 6가지이고 장애물이 있을 때에는 2가지이다. 

 

 한 칸 아래 또는 한 칸 오른쪽으로 갈 수 있으므로 점화식은 f(m, n) = f(m-1, n) + f(m, n-1)이다. 장애물 같은 경우는 갈 수 있는 경우의 수가 0이므로 0으로 설정해준다. 

 

 

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

int a[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0; i<puddles.size(); i++){
        a[puddles[i][0]][puddles[i][1]] = -1;
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(i==1 && j==1) a[i][j] = 1;
            else if(a[i][j] == -1) a[i][j] = 0;
            else a[i][j] = (a[i-1][j] + a[i][j-1])%1000000007;
        }
    }
    return a[m][n];
}

 

 

 결과는 통과하였다.