백준[1890] 점프

아이디어

[DP]를 사용할줄 안다

접근방식

1. 점프 값을 저장하기 위한 2차배열, 각 위치에서의 dp를 저장하기 위한 2차배열을 만들되, dp는 long long으로 만든다(값이 int보다 커질 수 있음)
2. 0,0에서의 dp값은 1로 초기화 해준다
3. 2차원배열을 (0,0) ~ (n-1,n-1) 까지 조사하며, 점프한 위치의 dp값에 현재위치의 dp값을 계속해서 더해준다. 단, 조사할때는 dp값 > 0 일때만 조사해준다. (0이 아닌 값은 (0,0)에서 방문할 수 없는 위치이기 때문)

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
#include <queue>

#define MAX 987654321

using namespace std;

int board[100][100];
long long int dp[100][100];
int n;


int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int num; scanf("%d", &num);
			board[i][j] = num;
		}
	}

	dp[0][0] = 1;

	for (int col = 0; col < n; col++)
	{
		for (int row = 0; row < n; row++)
		{
			if (board[col][row] == 0) continue;

			if (dp[col][row] != 0)
			{
				int next_row = row + board[col][row];
				int next_col = col + board[col][row];

				if(next_col < n) dp[next_col][row] += dp[col][row];
				if(next_row < n) dp[col][next_row] += dp[col][row];
			}
		}
	}

	printf("%lld", dp[n - 1][n - 1]);


	return 0;
}

평가

생각보다 구현하기 쉬운 dp문제.
저는 처음에 각 위치별로 들어올 수 있는 가지수를 전부 조사하려고 했습니다. 하지만 그렇게하면 단점이, (0,0)에서 도달할 수 없는 위치의 가지수도 더해진다는 점이 오점이었습니다.
또한 bfs, dfs등으로 조사시, 재귀 함수의 개수가 굉장히 많이 늘어나( 2의 승개로 불어남) 조사가 힘들다는 것을 깨달았었습니다.
계속해서 고민 하던중, 전체를 조사하되, 방문할 수 있는 위치만 조사하게끔 만들었습니다.
또한, 값이 2^63-1 보다 작다는 것에서, int보다 값이 커질 수 있겠다는걸 예측할 수 있었습니다.

• 배울 것 :
  1) 값이 너무 커지면 DP를 의심해볼 것
  2) 2차원 배열 문제도 꼭 bfs, dfs가 아닐 수 있다