문제는 여기에서 풀 수 있습니다.
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;
}
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ] 11048 이동하기 (2) | 2020.01.12 |
|---|
