[백준] 11060번 : 점프 점프 - JAVA [자바]

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

---

문제

 

위 문제는 DP 풀이법으로 풀었다.

 

아래의 문제와 유사하다.

https://bean-conding.tistory.com/16

[백준] 11048번 : 이동하기- JAVA [자바]

 

당연히 Memonization 기법을 통해서 DP 배열에 점프한 횟수의 최솟값을 비교하며 다음 DP칸에 저장했다.

하지만 채점결과 100%에서 틀렸다고 나왔고 한참을 고민한뒤에 내가 큰 실수를 했다는 것을 깨닫았다.

 

마지막 출력 코드에서 실수를 했다.

// 출발점 위치가 목적지인 경우
if(N == 1) {
	// 여기 부분을 System.out.println(1)이라고 했다......
   	System.out.println(0);
}
// 만약 마지막 DP 인덱스 값이 0이라면 갈 수 없음으로 -1출력
else if(DP[N - 1] == 0) {
   	System.out.println(-1);
 }
// 목적지까지 갈 수 있을 경우. 
 else {
   	System.out.println(DP[N - 1]);
 }

 

히든 케이스를 생각하며 출발지와 목적지가 같으면 -1을 출력하는 것을 보고 너무나 당연하게도 1로 출력하도록 만들었다.

하지만 출발지와 목적지가 같다면 점프할 일이 없기때문에 0을 출력해야된다.

 

이 문제가 코딩테스트 문제로 나왔다면 나는 아깝게 틀린것이다.

분하다. 다시는 이런 실수를 범하지 말아야겠다. 

---

전체 코드

package main;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int N;
	static int[] arr;
	static boolean[] possible;
	
	public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("input.txt"));
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();
    	StringTokenizer st;
    	
    	N = Integer.parseInt(in.readLine());
    	arr = new int[N];
    	possible = new boolean[N];
    	
    	st = new StringTokenizer(in.readLine());
    	
    	for(int i = 0; i < N; i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// DP 로직 시작.
    	int[] DP = new int[N];
    	possible[0] = true;
    	
    	for(int i = 0; i < N; i++) {
    		int step = arr[i];
    		
            // 현재 위치가 도달하기가 불가능하면 다음 블럭으로.
    		if(!possible[i]) continue;
    		
    		for(int j = 1; j <= step; j++) {
    			int next = i + j;
    			
    			if(next < N) {
    				possible[next] = true;
    				
    				if(DP[next] != 0) {
    					DP[next] = Math.min(DP[next], DP[i] + 1);
    				}
    				else {
    					DP[next] = DP[i] + 1;
    				}
    			}
    		}
    	}
    	
    	// 출발점 위치가 목적지인 경우
    	if(N == 1) {
    	   	System.out.println(0);
    	}
    	// 만약 마지막 DP 인덱스 값이 0이라면 갈 수 없음으로 -1출력
    	else if(DP[N - 1] == 0) {
    	   	System.out.println(-1);
    	 }
    	// 목적지까지 갈 수 있을 경우. 
    	 else {
    	   	System.out.println(DP[N - 1]);
    	 }
    }
}

 

---

결과