DP를 이용한 문제였다.
경로의 경우의 수를 구하는 문제였으며 어렵지 않게 풀었다.
(0 , 0) 은 항상 1이며 현재 좌표에서 다음좌표로 갈 수 있으면 값을 누적 시키면서 더해주면 된다.
문제링크 : 1890번: 점프 (acmicpc.net)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int N;
cin >> N;
vector<vector<long long>> DP(N, vector<long long>(N, 0));
vector<vector<int>> map(N, vector<int>(N, 0));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> map[i][j];
DP[0][0] = 1;
for(int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
if (i == N - 1 && j == N - 1)
break;
if (DP[i][j] == 0)
continue;
else
{
if (i + map[i][j] < N)
DP[i + map[i][j]][j] += DP[i][j];
if (j + map[i][j] < N)
DP[i][j + map[i][j]] += DP[i][j];
}
}
cout << DP[N - 1][N - 1] << '\n';
return 0;
}
'Coding_Test 연습 > Baekjoon Online Judge' 카테고리의 다른 글
[BOJ] (C++) 14002 가장 긴 증가하는 부분 수열 4 (0) | 2022.09.10 |
---|---|
[BOJ] (C++) 2096 내려가기 (0) | 2022.09.09 |
[BOJ] (C++) 9655 돌 게임 (0) | 2022.09.08 |
[BOJ] (C++) 1309 동물원 (0) | 2022.09.07 |
[BOJ] (C++) 11660 구간 합 구하기 5 (0) | 2022.09.06 |