[백준 1890] 점프

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

 

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

---

접근

처음에는 DFS로 접근을 했는데 시간초과가 발생했다. 

다른 사람들의 풀이를 참고했을 때 동적계획법으로 푸는 것을 알았다.

어떻게 동적계획법으로 풀까를 생각해봤을 때 각 지점마다 올 수 있는 경로의 개수를 기록해나가도록 한다.

 

(0, 0)에서 시작을 해서 해당 칸의 수만큼 오른쪽과 왼쪽으로 진행하면서 이전의 경로의 수에서 +1을 해주도록 한다. 이렇게 신뢰성있게 기록을 해나가면 끝에가서는 해당 기록을 통해 최종해를 구할 수 있다.

 

구현

경로의 수를 기록해두는 dp배열은 int형이 아닌 long long형으로 선언을 한다. 경로의 개수가 2^63-1이하이기 때문이다.

	int N;
	int map[101][101];
	long long dp[101][101] = { 0, };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

 

처음 시작점인 (0, 0)은 경로의 수가 1이기 때문에 1을 기록해두고 시작을 한다.

이제 2차원 탐색을 진행하고, 해당 칸에 적힌 수를 jump에 저장하고 해당 수만큼 오른쪽 또는 왼쪽으로 점프를 한다. 이때 맵의 범위를 벗어나거나 도착점에 도달했을 때는 벗어나도록 한다. 도착점은 0이기 때문에 해당 자리에서 제자리로 점프를 하는 경우도 추가될 수 있다.

	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int jump = map[i][j];
			if (i == N - 1 && j == N - 1)
				break;
			if (i + jump < N) {
				dp[i + jump][j] += dp[i][j];
			}
			if (j + jump < N) {
				dp[i][j + jump] += dp[i][j];
			}
		}
	}

---

전체 코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;


int main()
{
	int N;
	int map[101][101];
	long long dp[101][101] = { 0, };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int jump = map[i][j];
			if (i == N - 1 && j == N - 1)
				break;
			if (i + jump < N) {
				dp[i + jump][j] += dp[i][j];
			}
			if (j + jump < N) {
				dp[i][j + jump] += dp[i][j];
			}
		}
	}
	cout << dp[N - 1][N - 1] << endl;

	return 0;
}