동적 계획법을 사용하는 문제였다 열심히 풀어보려했지만 한계점까지 풀고 결국 힌트를 얻어서 풀 수 밖에 없었다.. 아직 dp를 활용하는 방법이 익숙하지 않은 것 같다
package S1_Baekjoon;
import java.util.*;
public class Baekjoon1890 {
public static void main(String[] args){
//가장 왼쪽 위 칸에서 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것
//각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리
//오른쪽이나 아래로만 이동
//0은 종착점
//항상 현재 칸에 있는 수만큼 오른쪽이나 아래로 가야함
//규칙에 맞게 이동할 수 있는 경로의 개수 구하기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 0;
int[][] NN = new int[N][N];
int[][] Ntest = new int[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
NN[i][j] = sc.nextInt();
}
}
//첫 번 째 경우의 수 1 * 1 * 1
//1 * 1 * 2 * 1
//인덱스의 배열에 있는 값이 인덱스의 값보다 크면 못감 위 아래로 기준
//첫 인덱스가 1,1 이니 더 커지는 경우에만 조건으로 판단
// 오른쪽 왼쪽으로 갈 수 있을 경우에 경우의 수 1 씩추가
int i = 0;
int j = 0;
while(true){
if(i < N && j < N) {
int sample = NN[i][j];
NN[i][j] = NN[i + sample][j];
NN[i][j] = NN[i][j + sample];
}
}
}
}여기까지가 내가 푼 정도 였다
i 와 j 의 길이가 N 보다 크지 않게 하면서
배열에 배열값을 추가하면서 진행시키는 부분까지는 할 수 있었으나
여기부터 막히기 시작했다
답은 아래로 가는 경우와 오른쪽으로 가는 경우의 개별적 처리를 해주면 됬다
dp배열에서 이동 가능한 경로의 수를 1로 설정하고 그 다음 왼쪽 상단부터 오른쪽 아래까지 순회하면서 이동 가능한 오른쪽 칸과 아래쪽 칸으로 dp[][] 값을 전달한다
전달하는 방법은
dp[이동할 칸] += dp[현재 칸] 이다.
현재 칸에서 이동할 수 있는 모든 경로의 수를 이동할 칸에 더하는 것
어떻게 구동되는지 코드만 보고는 판단하기 어려울 수 있다 그래서 그림으로도 그려봤다
NN은
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0dp는
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0이렇게 시작된다
1단계 i = , j = 0일때 dp[0][0] = 1dlek. 그리고 board[0][0] 값은 2d이다 그래서 오른쪽으로 2칸 점프하거나 아래로 2칸 점프할 수 있다. 그러므로 dp[0][2]와 dp[2][0]에 현재의 dp[0][0]값을 더해준다.
1 0 1 0
0 0 0 0
1 0 0 0
0 0 0 02단계 : i = 0 j = 2일 때 dp[0][2] = 1이다. 그리고 board[0][2]값은 3이므로 오른쪽으로 3칸 점프하거나 아래로 3칸 점프할 수 있다.
하지만 오른쪽은 값이 넘어버려서 점프가 불가능하니 dp[3][2]에 현재의 dp[0][2]값을 더해준다
1 0 1 0
0 0 0 0
1 0 0 0
0 0 1 0
3단계 : i = 2 , j = 0 일 때, dp[2][0] = 1이다 그리고 NN[2][0]의 값은 1이다. 그러므로 오른쪽으로 1칸 , 아래로 1칸 가능하다
dp[2][1]과 dp[3][0]에 현재의 dp[2][0] 값을 더해준다
1 0 1 0
0 0 0 0
1 1 0 0
1 0 1 0
이런 식으로 진행해서 결과적으로
1 0 1 0
0 0 0 0
1 1 0 0
1 0 1 3이렇게 출력이 나오게 된다
package S1_Baekjoon;
import java.util.*;
public class Baekjoon1890 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] NN = new int[N][N];
long[][] dp = new long[N][N]; //경로의 수가 매우 클 수 있으므로 long 타입
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
NN[i][j] = sc.nextInt();
}
}
dp[0][0] = 1; //시작접의 경로 수는 1
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(NN[i][j] == 0){
continue; //도착점은 패스
}
if(j + NN[i][j] < N){ //오른쪽으로 이동할 경우
dp[i][j + NN[i][j]] += dp[i][j];
}
if(i + NN[i][j] < N){ //아래쪽으로 이동할 경우
dp[i + NN[i][j]][j] += dp[i][j];
}
}
}
System.out.println(dp[N-1][N-1]);
}
}