프로그래머스 Level 3 등굣길

등굣길 (프로그래머스 Level 3)

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

오랜만에 풀어본 DP 문제였다
아이디어 자체는 재귀적으로 풀기 쉬웠지만
시간 복잡도에 대하여 2번 정도 고민하다
침몰 지역에 대한 접근 방식과
‘기존에 계산한 값’을 재이용하는 점을 다시 생각하여 풀었다

1. 침몰 지역에 대한 접근 방식
   

   처음에는 puddles를 for문을 돌려 풀었다
   침몰 지역이 10개 이하라고 하니 괜찮겠지…
   싶었지만 각 재귀마다 10개씩 호출되는 부분이 문제일 수 있겠다 싶어
   solution 내부에 m X n 개의 bool 배열을 잡아두었고,
   이후 O(1)로 접근하는 방식으로 고쳤다
   

2. 1을 바꿨으나 여전히 시간 효율성 문제가 풀어지지 않아 고민하다가
   DP는 ‘이전에 활용한 값을 재활용’ 하는 부분이 떠올라
   메모이제이션 용 배열을 추가하고,
   계산한 값을 넣어주었다
   이후, 내부에 값이 있다면 그 값을 사용하도록 바꾸었다
   

Code

#include <string>
#include <vector>

using namespace std;

int dp(int x, int y, int m, int n,const vector<vector<bool>>& p , vector<vector<int>>& memo)
{
	if (x > m)
		return 0;

	if (y > n)
		return 0;

	if (p[x][y])
		return 0;

	if (memo[x][y] != 0)
		return memo[x][y];

	if (x == m && y == n)
		return 1;

	return memo[x][y] = (dp(x + 1, y, m, n, p, memo) + dp(x, y + 1, m, n, p, memo)) % 1000000007;
}

int solution(int m, int n, vector<vector<int>> puddles) {
	vector<vector<bool>> p(vector<vector<bool>>(m + 1, vector<bool>(n + 1, false)));
	vector<vector<int>> memo(vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));

	int width = puddles.size();

	for (int i = 0; i < width; i++)
	{
		int xValue = puddles[i][0];
		int yValue = puddles[i][1];

		p[xValue][yValue] = true;
	}

	int answer = dp(1, 1, m, n, p,memo);

	return answer % 1000000007;
}