백준1890 - 점프

https://www.acmicpc.net/problem/1890ㅇ

1890번: 점프

오랜만에 다이나믹 프로그래밍 문제를 풀었다. 탐색으로는 도저히 풀 수 있는 방법이 없었고 이동 가능한 방향이 오른쪽과 아래로 주어져 있기 때문에 다이나믹 프로그래밍으로 접근하였다. 현재 위치에서 갈 수 있는 거리가 주어지고 그 거리가 유효한 좌표 범위이면 도달 가능하다고 구하였다. 중요한 것은 도달할 수 없는 곳은 건너뛴다는 것이다. 또한 마지막 도착점은 0으로 주어지기 때문에 도착점에서 다이나믹 프로그래밍을 이용하여 비용을 구하면 잘못된 비용이 나오기 때문에 도착점을 건너뛴다는 것도 중요하다.

 

#include <iostream>
#define MAX 101
using namespace std;

int n; //정사각형 한 변의 길이
int mat[MAX][MAX] = { 0 }; //(x, y)에서 이동해야 되는 거리
long long int d[MAX][MAX] = { 0 }; //(x, y)에 도달할 수 있는 방법의 수

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> mat[i][j];
		}
	}

	d[1][1] = 1; //출발지점은 1로 설정

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == 0 || (i == n && j == n)) { //도착할 수 없는 곳이나 마지막 칸을 만나면
				continue; //무시
			}
			if (1 <= i + mat[i][j] && i + mat[i][j] <= n) { //현재 위치에서 행 방향으로 도달할 수 있는 곳이면
				d[i + mat[i][j]][j] += d[i][j]; //가려하는 곳의 방법의 수를 현재 위치에 도달할 수 있는 방법과 더한다.
			}
			if (1 <= j + mat[i][j] && j + mat[i][j] <= n) { //현재 위치에서 열 방향으로 도달할 수 있는 곳이면
				d[i][j + mat[i][j]] += d[i][j]; //가려하는 곳의 방법의 수를 현재 위치에 도달할 수 있는 방법과 더한다.
			}
		}
	}

	cout << d[n][n];
}