[백준] 점프 점프 (11060번 JAVA) / DP

[백준] 점프 점프 (11060번 JAVA) / DP

---

[접근 방법]

arr 배열로 Ai 배열을 입력 받는다.

DP 배열은 현재 위치 까지 이동하는데 소요된 "최소 점프 수" 이다.

 

현재 위치인 2에서 점프 가능한 칸 수가 3인 경우,

3, 4, 5으로 이동가능 하다.

따라서, DP[3], DP[4], DP[5] 값은 "DP[2] + 1" 으로 갱신 된다.

arr[3] = 2 이므로, 4, 5로 이동 가능하다.

이때, 기존 DP[4] 와 DP[5]에 값이 존재하므로,

기존 DP[4] = 2의 경우 (1 -> 2 -> 4) 와

(1 -> 2 -> 3 -> 4)의 경우 중 점프 횟수가 더 작은 값으로 갱신 한다. 

 

완성된 DP는 다음과 같다.

---

[JAVA 코드]

// 11060 - 점프 점프
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N+1];
        int[] DP = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // DP 배열 초기화
        Arrays.fill(DP, -1);
        DP[1] = 0;

        for(int i=1; i<=N; i++){

            // 이동 가능한 위치 모두 탐색
            for(int j = i+1; j<=i+arr[i]; j++){
                // OutOfIndex 방지
                if (j < N + 1){
                    if (DP[j] != -1){

                        // 현재 위치 까지 최소 이동 
                        DP[j] = Math.min(DP[i] + 1, DP[j]);
                    } else {
                        DP[j] = DP[i] + 1;
                    }
                }
            }
        }

        // DP 배열에 -1 이 존재 
        // = 끊켜 이동할 수 없는 지점이 존재
        boolean flag = true;
        for(int i=1; i<=N; i++){
            if (DP[i] == -1){
                flag = false;
                break;
            }
        }

        if (flag){
            bw.write(DP[N]+"\n");
        }else {
            bw.write(-1 + "\n");
        }

        bw.flush();
        
        bw.close();
        br.close();
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 반례를 찾는 것이 어려웠다.

- 찾은 반례를 예외처리하는 방법을 찾는 것이 어려웠다.

 

2. 알게된 점

- DP 점화식을 구하는 노하우를 습득하게 되었다.

 

3. 개선 방향

- 반례를 찾고 예외 처리에 신중해야 한다.