문제
N×N 게임판에서 각 칸의 숫자만큼 오른쪽 또는 아래로 점프할 수 있다. (1,1)에서 (N,N)까지 도달하는 경로의 수를 구하라.
입력
첫째 줄에 N (1 이상 100 이하), 이후 N×N 게임판이 주어진다. 오른쪽 아래 칸은 항상 0이다.
출력
경로의 수를 출력한다 (long 범위).
예제
| 입력 | 출력 |
|---|---|
4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 | 3 |
풀이
전방 DP로 각 칸에서 도달 가능한 칸에 경로 수를 누적한다.
dp[0][0] = 1로 시작점을 초기화한다- (0,0)부터 (N-1, N-1) 직전까지 순회한다
- 현재 칸의 숫자
next만큼 아래(dp[i+next][j])와 오른쪽(dp[i][j+next])에dp[i][j]를 더한다 - 범위를 벗어나는 점프는 무시한다
dp[N-1][N-1]을 출력한다
핵심 아이디어: 전방 전파 DP로 각 칸에서 도달 가능한 칸에 경로 수를 누적한다. 점프 크기가 고정이므로 각 칸에서 최대 2개 칸만 갱신한다.
코드
import java.io.*;
public class Day357BOJ1890점프DP {
static int N;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][N + 1];
long[][] dp = new long[N + 1][N + 1];
String str[];
for (int i = 0; i < N; i++) {
str = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(str[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)
continue;
int next = arr[i][j];
if (i + next < N) {
dp[i + next][j] += dp[i][j];
}
if (j + next < N) {
dp[i][j + next] += dp[i][j];
}
}
}
System.out.println(dp[N - 1][N - 1]);
br.close();
}
}복잡도
- 시간: O(N^2) - 격자 전체 순회
- 공간: O(N^2) - DP 배열