BaekJoon 1890번: 점프(C++)

https://www.acmicpc.net/problem/1890

1890번: 점프

 

풀이법

1) 얼핏 보면 경로의 개수를 세면 되니 방문한 곳을 세지 않고 반복하는 dfs를 사용하면 되는 문제처럼 보이나 dfs를 사용하게 된다면, 시간 초과가 발생한다.

2) 마찬가지로 bfs를 사용하게 되면 메모리 초과가 나서 문제를 해결 할 수 없다. 모든 map이 1로 가득 차 있는 경우 경우의 수가 너무 많아지기 때문이다.

3) 문제를 해결함에 있어 2차원 dp 배열을 만들어서 해결하였다. 가능한 경우의 수는 pow(2,63)-1개 까지 가능하기에, int로 dp 배열을 만들게 되어도 실패할 수 있다. 고로 long long type으로 사용하였다.

4) 중간에 입력 배열 중 0 이 있는 경우가 있을 수 있다. 이 경우 dp 값을 갱신하지 않는 것으로 코딩을 진행하였다.

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dp[i][j] == 0 || (i == n - 1 && j == n - 1))
				continue;
			int value = arr[i][j];
			int down = i + value;
			int right = j + value;

			if (down < n)
				dp[down][j] = dp[down][j] + dp[i][j];
			if (right < n)
				dp[i][right] = dp[i][right] + dp[i][j];
		}
	}

점화식은 다음과 같다. 

값이 배열의 크기를 벗어날 경우 새롭게 갱신하지 않으며, 해당 x index와 y index에 접근할 수 있는 경우 기존의 값에, 새로운 길을 더해주는 방식으로 문제를 해결하였다.

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define INF 987654321
using namespace std;

int n;
int arr[101][101];
long long dp[101][101];
long long cnt = 0;
//dfs로 풀면 시간초과, bfs로 풀면 메모리 초과

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}
	dp[0][0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dp[i][j] == 0 || (i == n - 1 && j == n - 1))
				continue;
			int value = arr[i][j];
			int down = i + value;
			int right = j + value;

			if (down < n)
				dp[down][j] = dp[down][j] + dp[i][j];
			if (right < n)
				dp[i][right] = dp[i][right] + dp[i][j];
		}
	}
	cout << dp[n - 1][n - 1];
}