11060 점프 점프

 

1. 풀이

 

문제에서 주어진 예시를 가지고 설명하겠다.

 

10
1 2 0 1 3 2 1 5 4 2

 

input 배열에 입력값을 입력한다.

1 2 0 1 3 2 1 5 4 2 => input 배열에 입력

 

dp[i] 배열값은 첫번째 위치에서 i 번째까지 점프한 횟수이다.

 

 

1) i = 0 

dp[0] = 0 

첫번째 칸은 시작 칸으로 이동이 없으므로 0으로 초기화된다.

input[0] = 1 이므로, 오른쪽으로 한 칸 점프 가능하다.

=> i = 1 위치까지 점프

 

2) i = 1

dp[0] 에서 점프가 1번 더해졌으므로

dp[1] = dp[0] + 1 =1

 

input[1] = 2이므로, 오른쪽으로 한 칸, 두 칸까지 이동 가능하다.

=> i = 2, 3까지 이동

 

3) i = 2

dp[2] = dp[1] + 1 = 2

input[2] = 0 이다.

=> 오른쪽으로 점프 불가능.

 

4) i = 3

dp[3] = dp[1] + 1 = 2

input[3] = 1

=> i = 4 까지 이동.

 

이런식으로 dp 값을 채워주고, 정답으로 dp[N-1] 값을 출력하면 된다.

 

 

2. 주의할 점 

 

위의 과정을 하다보면, 

 

i= 4 일때,

dp[4] = 3 이다.

input[4] = 3 이므로,

=> i = 5,6,7 까지 이동 가능하다.

 

그러면 

dp[5] = dp[4] + 1 = 4

dp[6] = dp[4] + 1 = 4 

dp[7] = dp[4] + 1 = 4

이 될 것이다.

 

그런데,

i = 5 일때,

input[5] = 2 이므로,

i = 6, 7 까지 이동 가능하다.

 

그러면

dp[6] = dp[5] + 1 = 5

dp[7] = dp[5] + 1 = 5 가 된다.

 

즉, 위의 i = 4 일때 입력한 dp[6], dp[7] 값이 다시 새로운 값으로 채워지게 된다.

그런데 문제에서 최소 점프를 통해 가장 오른쪽 끝 칸으로 가라고 했으므로

더 작은 값, 즉 dp[6] = dp[4] +1 = 4 가 되어야 한다.

그래서, dp값이 이미 채워져 있다면, 즉 0이 아니라면 dp 값을 새롭게 채우지 못하도록 했다.

 

3. 최종 코드

 

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


public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		int input [] = new int[N];
		
		for(int i=0; i<N;i++ ) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		
		int dp[] = new int[N];
		dp[0] = 0;
	
		
		if(N ==1 && input[0] ==0) {
			System.out.println(0);
			return;
		}
		
		int i = 0;
		
		solve :
		while(i<N-1) {
	
			for(int j =i+1; j<=i+input[i]; j++) {
			
				if(j>=N) {
			
					break solve;
				}
	
				if(dp[j]==0) {
					dp[j] = dp[i] + 1;
				}
			}
		
			if(input[i] == 0 && dp[i+1] ==0) {
				break solve;
			}
		
			i++;
		}
		
		
		if(dp[N-1] ==0 ) {
			System.out.println(-1);
		}else {
			System.out.println(dp[N-1]);
		}
		
	}
}