[DP]점프 점프(백준 11060번), 자바

11060번: 점프 점프 (acmicpc.net)

11060번: 점프 점프

고려해야 하는 반례

#1

input

3

0 3 4

output: -1

 

#2.

input

5

1 0 0 1 0 

output: -1

import java.util.*;

public class Main2 {
	
	
	public static void main(String[] args){
	
		Scanner sc=new Scanner(System.in);
		int N;
		N=sc.nextInt();
		int[]dp=new int[N];
		int[] d=new int[N];
		for(int i=0;i<N;i++) d[i]=sc.nextInt();
		dp[0]=1;
		if(d[0]!=0) {
			for(int i=0;i<N;i++) {
				if(d[i]==0 || dp[i]==0) continue;
				for(int j=1;j<=d[i] && i+j<N;j++ ) {
					if(dp[i+j]==0) dp[i+j]=(dp[i]+1);
					else dp[i+j]=Math.min(dp[i]+1,dp[i+j]);
				}
			}
		}
		System.out.println(dp[N-1]-1);
	}
}