[백준/JAVA] 1890번: 점프

🔺 문제

1890번: 점프

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N + 1][N + 1];
        
        // 입력 받기
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 1 ; j <= N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // DP 배열 채우기
        long[][] dp  = new long[N + 1][N + 1];
        dp[1][1] = 1;
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                int next = map[i][j];
                
                if(i == N && j == N) continue;
                
                // 오른쪽으로 이동
                if(j + next <= N)   
                    dp[i][j + next] += dp[i][j];
                
                // 아래쪽으로 이동
                if(i + next <= N)
                    dp[i + next][j] += dp[i][j];
            }
        }        
        
        System.out.println(dp[N][N]);
    }
}

✅ 해결 아이디어
✔ DP
1) 테이블 정의
 - dp[i][j] = (i, j) 위치 까지 도착하는 경우의 수
2) 점화식 찾기
 - 오른쪽으로 이동하는 경우 : dp[ i ] [ j+ map[i][j] ] += dp[i][j]
 - 아래로 이동하는 경우        : dp[i + map[i][j] ] [ j ] += dp[i][j]
3) 초기값 설정
 - dp[1][1] = 1;

 

 

---

🔺 다른 풀이들

- dp 배열 채우는 부분이 조금 다르심

[BOJ] 백준 1890번 : 점프 (JAVA)

---

💬 느낀 점

점화식 찾아놓고 헤매고 있던 나 바보....

 

 

1회독	2회독	3회독	4회독	5회독
V	240309

 

 

(+ 240309 2회독 : 14300KB, 124ms)

import java.util.*;
import java.io.*;
 
public class Main {
    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));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        board = new int[N+1][N+1];
        
        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 = new long[N+1][N+1];
        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 val = board[i][j];
                
                // 오른쪽으로 이동
                if(j + val < N)
                    dp[i][j + val] += dp[i][j];
                
                // 아래쪽으로 이동
                if(i + val < N)
                    dp[i + val][j] += dp[i][j];
            }
        }
        
        System.out.println(dp[N-1][N-1]);
    }
}
 

---

(참고)

✔ 과정 설명 굿... 놓친 부분을 깨달았습니다 감사합니다....

[JAVA] 백준 1890번 : 점프