[백준/11060] 점프 점프 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버2
출처 : 백준 - 점프 점프

🦧 문제 풀이 접근

dp배열에 모든 인덱스에 -1 값을 넣는다.
0번째 칸부터 입력받은 숫자 만큼 뒤로 가면서 -1일 경우 dp[i]+1의 값을 넣고, -1이 아닐경우 dp[i]+1과 해당 칸의 값 중 더 작은 값을 넣는다.

💻 code

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 dp[] = new int[N];
        dp[0] = 0;
        for(int i=1;i<N;i++) {
            dp[i]=-1;
        }
        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            if(dp[i]==-1)
                continue;
            for(int j=i+1;j<Integer.min(N,i+num+1);j++) {
                if(dp[j]==-1)
                    dp[j] = dp[i]+1;
                else
                    dp[j] = Integer.min(dp[i]+1,dp[j]);
            }
        }
        System.out.println(dp[N-1]);
    }
}

🥇 결과

🎓 느낀점

간단한 dp문제이지만 반복문의 범위를 잘 설정해야 한다.