BOJ S1 1890 점프 JAVA

1890번: 점프

---

 

문제 읽기

 

처음에 딱 문제를 읽었을 때는 .. DP인 걸 인지하고 있었기 때문에 이중 for문을 쓰면서 채워나갈 수 있을 것이라 생각했다.

하지만 계속 읽다 보니 (0, 0)에서 시작하여 (N-1, N-1) 지점까지 DFS 또는 BFS를 써도 되지 않을까 하는 생각이 들었다.

일단 시뮬레이션을 해봤을 때 DFS가 더 맞는 것 같았지만, 문제의 조건에서도 볼 수 있듯이 판의 크기가 최대 100이다. DFS 쓰면 2^100…. 무조건 시간초과이다.

그래도 한 번 해봤는데 (당연하게도) 시간초과가 나왔다.

 

그냥 처음 생각대로 풀어보자.

 

---

문제 풀기

문제에서 주의할 점은 다음 세 가지가 있다.

1. 판의 크기 N : 4~ 100
2. 칸에 적힌 숫자 : 0~9 (이건 사실 크게 중요하진 않고)
3. 경로의 개수 : 2^63-1 이하
4. ⇒ int 불가능. DP 배열은 long으로 설정하자

값의 범위

int : 32비트 = +-20억
long : 64비트 = 그 이상

 

 

즉, 게임판 배열은 int[][], DP 배열은 long[][]으로 선언해주고,

dp[0][0]만 1로 초기화해준 뒤, 이중 for문을 통해 모든 배열을 탐색하며 해당 지점의 위쪽, 왼쪽 값들만 봐준다.

 

그림으로 설명하면 다음과 같다.

 

 

2차원 for문을 돈다

1. 우선 DP 판을 보자.
2. (3, 2) 지점, 즉 노란색 지점의 DP 값을 채우고 싶다.
3. 그러면 노란색 지점에 영향을 줄 수 있는 부분은 위와 같이 파란색으로 칠한 부분이다.
4. 게임판에서 파란색으로 칠한 부분을 보면,
   1. 노란색 칸과 한 칸 차이 나는 칸에는 1이 있으면 되고,
   2. 노란색 칸과 두 칸 차이 나는 칸에는 2가 있으면 되고,
   3. 노란색 칸과 세 칸 차이 나는 칸에는 3이 있으면 된다.
   4. 이를 게임판에 빨간색으로 적어두었다.
   이를 만족하는 칸은 (3, 1), (0, 2)이고, 이를 DP 칸의 값을 찾아 더해주면 0 + 1 = 1이 들어감을 알 수 있다.

이와 같은 방식으로 모든 칸을 순회하면, DP[N-1][N-1]에서 원하는 답을 얻을 수 있다.

이처럼 DP를 활용하면 NN(2N/2) = N^3의 시간 복잡도를 가져 DFS보다 훨씬 효율적으로 해결할 수 있다.

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_S1_1890_점프 {
    static int N;
    static int[][] map;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        map = new int[N][N];
        dp = new long[N][N];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //dp
        dp[0][0] = 1;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                //위쪽
                int cnt = 1;
                for (int up = i-1; up >= 0; up--){
                    if (cnt == map[up][j]) dp[i][j] += dp[up][j];
                    cnt++;
                }
                //왼쪽
                cnt = 1;
                for (int left = j-1; left >= 0; left--){
                    if (cnt == map[i][left]) dp[i][j] += dp[i][left];
                    cnt++;
                }
            }
        }

//        for (int i = 0; i < N; i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }
        System.out.println(dp[N-1][N-1]);
    }

}