[BOJ] (C++) 1890 점프

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;
}