https://www.acmicpc.net/problem/1890
1890번: 점프
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로
www.acmicpc.net
더보기
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<vector<int>> arr;
vector<vector<unsigned long long>>dp;
cin >> n;
arr.resize(n + 1);
dp.resize(n + 1);
for (int i = 1; i <= n; i++) {
arr[i].resize(n + 1);
dp[i].resize(n + 1);
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
}
}
dp[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k < i; k++) {
if (k == arr[i - k][j]) {
dp[i][j] += dp[i - k][j];
}
}
for (int k = 1; k < j; k++) {
if (k == arr[i][j - k]) {
dp[i][j] += dp[i][j - k];
}
}
}
}
/*for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << dp[i][j] << " ";
}
cout << "\n";
}*/
cout << dp[n][n];
return 0;
}
'Algorithm > Algorithm 문제 풀이' 카테고리의 다른 글
| [BAE/<JOON> 문제풀이] 1309. 동물원 (DP.035) (0) | 2020.05.10 |
|---|---|
| [BAE/<JOON> 문제풀이] 2225. 합분해 (DP.034) (0) | 2020.05.09 |
| [BAE/<JOON> 문제풀이] 1520. 내리막길 (DP.032) (0) | 2020.05.07 |
| [BAE/<JOON> 문제풀이] 11054. 가장 긴 바이토닉 부분 수열 (DP.030) (0) | 2020.05.05 |
| [BAE/<JOON> 문제풀이] 가장 긴 감소하는 부분 수열 (DP.029) (0) | 2020.05.05 |