눈누난나

문제는 여기에서 풀 수 있습니다.

bfs를 쓸까 하다가 경로의 개수가 상당히 많아지는 것을 보고 dp를 써야겠구나 싶었습니다.

진행방향이 오른쪽이나 아래 뿐이므로, 순차적으로 가능성의 개수를 dp로 풀어나가면 됩니다. 

dp배열의 값을 [가능성의 개수]로 정의했기 때문에 초기값(dp[0][0])을 1로 설정하고 NXN배열을 순차적으로 탐색합니다. 탐색 방향과 점프 방향이 같으므로, 딱히 가지치기 할 케이스가 없습니다.

문제를 풀면서 신경써야했던 부분은 가장 오른쪽 아래 칸에서 dp연산을 수행하지 않는 것과 경로의 수가 int범위를 넘어가므로 dp배열을 long long으로 선언하는 것이었습니다.

시간복잡도는 O(N^2)이고 N<=100이므로 빠르게 문제를 풀 수 있었습니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <unordered_set>
#include <cstring>
using namespace std;

int arr[101][101];
long long dp[101][101];

// main function
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	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 (arr[i][j])
			{
				if (i + arr[i][j] < N)
					dp[i + arr[i][j]][j] += dp[i][j];
				if (j + arr[i][j] < N)
					dp[i][j + arr[i][j]] += dp[i][j];
			}
		}
	}

	cout << dp[N - 1][N - 1];

	return 0;
}