등굣길

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

#include <string>
#include <vector>

using namespace std;


int solution(int m, int n, vector<vector<int>> puddles) {
	int answer = 0;
	//m: x , n : y
	int dp[101][101] = { 0, };

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			dp[i][j] = 1;//일단 모든 곳에 다 1로 갈수 있다고 도배한다.
		}
	}

	for (int i = 0; i < puddles.size(); i++)//0 : x이고 1 : y이다.
	{
		int x = puddles[i][0]-1;//좌표를 위한 마이너스 1처리가 되있지않았음.
		int y = puddles[i][1]-1;	


		if (x == 0)
		{
			for (int j = y; j < n; j++)///x가 영일 때 y부분들을 전부 0처리한다. 
			{
				dp[j][0] = 0;
			}
		}
		

		if (y == 0)
		{
			for (int j = x; j < m; j++)//y가 0일때 x부분들을 전부 0처리한다/
			{
				dp[0][j] = 0;
			}
		}
		

		dp[y][x] = 0;///물웅덩이로 인해서 길을 갈 수 없는 부부입니다.
	}

	for (int i = 1; i < n; i++)//y좌표
	{
		for (int j = 1; j < m; j++)//x좌표
		{
			if (dp[i][j]==0) continue;

			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j])%1000000007;
		}
	}

	return dp[n-1][m-1];
}




int main()
{

	int m(4);
	int n(3);

	vector<vector<int>> vvTemp = { {2,2} };




	int iTemp = solution(m, n, vvTemp);


	return 0;
}

이문제 풀 때 점화식은
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j])%1000000007;

for (int i = 1; i < n; i++)//y좌표
{
	for (int j = 1; j < m; j++)//x좌표
	{
		if (dp[i][j]==0) continue;
        이 식이 있는데,
        dp[i][j] = 0 일 때, 알아서 점화식에 0이 들어간다는걸 이해하는게 중요함.
        내가 약한 DP유형의 문제.