등굣길
2019, Jun 02
- https://programmers.co.kr/learn/courses/30/lessons/42898
- 격자에서 갈 수 있는 경우의 수를 찾는 dp 문제 입니다.
- 점화식은
dp[i][j] = dp[i-1][j] + dp[i][j-1]
입니다. - 문제에서 추가된 조건인 갈 수 없는 곳은 0으로 두면 점화식을 그대로 사용할 수 있습니다.
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
vector<vector<int>>dp(n + 2, vector<int>(m + 2, 0));
dp[1][1] = 1;
for (auto vec : puddles) {
int y = vec[1];
int x = vec[0];
dp[y][x] = -1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if(dp[i][j] == -1){
dp[i][j] = 0;
}
else {
dp[i][j] += dp[i][j - 1] + dp[i - 1][j];
dp[i][j] %= MOD;
}
}
}
answer = dp[n][m];
return answer;
}