등굣길

등굣길

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;
}