dp에 경로의 수를 저장하면서 도착 경로의 수를 구하는 문제이다.
원래는 해당 경로를 지났다는 표시만 하고 board[ i ] [ j ] 의 다음 목적지인 아래값이
x 축으로 이동하면 board[ i + board[ i ] [ j ] ] [ j ]
y 축으로 이동하면 board[ i ] [ j + board[ i ] [ j ] ]
목적지인 board[ N-1 ] [ N-1 ] 에 도달하면 count ++ 하는 방식으로 계산했는데
이렇게 하면 이전에서 겹치는 노드를 계산 할 수 없어서 실패.
문제풀이
이후에 dp 에 해당 노드에 도달한 수를 저장하는 방법으로 구현하였고
dp[ 0 ] [ 0 ] = 1로 초기값을 두고 다음 목적지 노드를 밟을때 해당 노드의 dp에
현재 노드 값을 더해가며 이동한 모든 노드의 합을 저장하였다
board[ 2 ] [ 2 ] 까지 가는 경우의 수는 2가지가 있으니 DP[ 2 ] [ 2 ] 의 값은 2이다
따라서 마지막 dp[ N-1 ][ N-1 ] 노드는 해당 노드까지의 모든 경우의 수를 저장하게 된다
주의할점
- 경로의 수 값은 2^63 - 1 보다 작거나 같으니 DP가 int타입이면 에러가 발생한다
- 다음 목표의 노드가 N-1 x N-1 크기를 벗어나는것을 주의하자
// https://www.acmicpc.net/problem/1890
// 점프
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B1890 {
static int N;
static int[][] board;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
board = new int[N][N];
dp = new long[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][0] = 1;
jump();
}
private static void jump() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(dp[i][j] == 0) continue;
if(i == N-1 && j == N-1) {
break;
}
if(board[i][j]+i < N){
dp[board[i][j]+i][j] += dp[i][j];
}
if(board[i][j]+j < N){
dp[i][board[i][j]+j] += dp[i][j];
}
}
}
System.out.println(dp[N-1][N-1]);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 11722 - 가장 긴 감소하는 부분 수열 (0) | 2022.09.13 |
---|---|
[백준 java] 11053 - 가장 긴 증가하는 부분 수열 (0) | 2022.09.12 |
[백준 java] 11048 - 이동하기 (2) | 2022.09.09 |
[백준 java] 10884 - 쉬운 계단 수 (0) | 2022.09.09 |
[백준 java] 11057 - 오르막 수 (0) | 2022.09.08 |