백준 11060번 점프점프 JAVA

별로 어려운 문제는 아니었는데 방문하지 않은 경우에 대해서 예외처리를 하지 않아서 계속 틀렸다..

문제의 핵심은 여느 DP가 그랬듯이 이전에 저장된 값을 이용해 비교하는 것 이다. 시간 복잡도는 배열의 개수 N개와 점프가 가능한 경우의 수들의 합인 M번을 반복해 O(NM)이 걸린다.

import java.io.*;
import java.util.Scanner;
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());
        int[] arr = new int[N];
        int[] go = new int[N];
        String temp = br.readLine();
        StringTokenizer st = new StringTokenizer(temp);
        int i=0;
        while (st.hasMoreTokens()){
            arr[i++]=Integer.parseInt(st.nextToken());
        }

        for(int j=0;j<N;j++){
            go[j]=9999999;
        }
        go[0]=0;
        for(int j=0;j<N;j++){
            for(int k=1;k+j<N&&k<=arr[j];k++){
                if(go[k+j]!=99999999){
                    go[k+j]=Math.min(go[j]+1,go[k+j]);
                }
            }
        }
        int answer=0;
        if(go[N-1]==9999999)
            answer=-1;
        else
            answer=go[N-1];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }
}