(c++)프로그래머스 코딩테스트 연습 - 등굣길

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

[풀이]

오른쪽과 아래로만 움직이면 갈 수 있는 지도의 면적이 작게 쪼개지므로 DP를 사용해 풀 수 있다.

점화식

DP[i][j] : (i,j)좌표로 가는 최단 경로의 수

DP[i][j] = DP[i-1][j] + DP[i][j-1]

#include <string>
#include <vector>

using namespace std;
const int D = 1000000007;

int dp[101][101];

void DP(int m, int n) {
	dp[1][1] = 1;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			//물에 잠긴 지역이면
			if (dp[i][j] == -1) {
				dp[i][j] = 0;
				continue;
			}
			if (i == 1 && j == 1)
				continue;
			//1행이면
			if (i - 1 < 1)
				dp[i][j] = dp[i][j - 1];
			//1열이면
			else if (j - 1 < 1)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % D;
		}
	}
}

int solution(int m, int n, vector<vector<int>> puddles) {
	int answer = 0;
	for (int i = 0; i < puddles.size(); i++) {
		dp[puddles[i][0]][puddles[i][1]] = -1;
	}
	DP(m, n);
	answer = dp[m][n] % D;
	return answer;
}