C++:: 프로그래머스 < 등굣길 >

전형적인 dp문제이다. 당연히 dfs와 같은 풀이로 구현하면 시간 초과가 나게된다.

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

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