(c++)백준 1890번: 점프

www.acmicpc.net/problem/1890

1890번: 점프

[풀이]

DP로 풀 수 있는 문제였다.

DP[i][j] : (1,1)에서 (i,j)까지 가는 경로의 수

점화식

if(i+Board[i][j]>N) : DP[i+Board[i][j]][j] = DP[i+Board[i][j]][j] + DP[i][j]

if(j+Board[i][j]>N) : DP[i][j+Board[i][j]] = DP[i][j+Board[i][j]] + DP[i][j]

 

#include <iostream>
#include <cstring>//memset
using namespace std;

int N;
int Board[101][101] = { 0, };
long long DP[101][101] = { 0, };

long long Range(int x, int y) {
	if (x > N || y > N)
		return 0;
	else
		return DP[x][y];
}

void solution() {
	DP[1][1] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (DP[i][j] == 0 || (i == N && j == N))
				continue;
			if (i + Board[i][j] <= N)
				DP[i + Board[i][j]][j] = DP[i + Board[i][j]][j] + DP[i][j];
			if (j + Board[i][j] <= N)
				DP[i][j + Board[i][j]] = DP[i][j + Board[i][j]] + DP[i][j];
		}
	}
	cout << DP[N][N] << '\n';
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Board[i][j];
		}
	}
	solution();
	return 0;
}