[프로그래머스] 등굣길

 

 

풀이

해보진 않았지만 dfs 로 풀면 시간초과가 될거라고 생각합니다. dp을 활용하여 각 블록까지 가는 경우의 수를 저장해나가며 풀었습니다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int mod = 1000000007;

int arr[101][101];
bool pArr[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    arr[1][1] = 1;

    for (auto& i : puddles) {
        pArr[i[1]][i[0]] = true;
    }
    
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (i == 1 && j == 1) continue;

            if(!pArr[i][j])
                arr[i][j] = arr[i - 1][j] % mod + arr[i][j - 1] % mod;
        }
    }
    
    return arr[n][m] % mod;
}