[백준OJ] 11060번 점프 점프

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

11060번: 점프 점프

---

 

풀이

DP를 이용해서 문제를 해결했다. 먼저 해당지점에서 점프했을때, dp[next]보다 더 작은횟수로 도달할 수 있다면 갱신을 해준다. 이때 점프를 했을때 범위를 넘어가면 안되므로 조건을 추가해준다.

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] v;
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        v=new int[n];
        dp=new int[n];

        for(int i=0;i<n;i++){
            v[i]=sc.nextInt();
        }
        sc.close();

        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;

        for(int i=0;i<n;i++){
            if(dp[i]==Integer.MAX_VALUE) continue;
            int canGo=v[i]+i;
            for(int j=i+1;j<=canGo&&j<n;j++){
                dp[j]=Math.min(dp[j],dp[i]+1);
            }
        }
        System.out.println(dp[n-1]==Integer.MAX_VALUE?-1:dp[n-1]);
    }
}