[백준] 11060 점프점프

문제보기

import java.util.*;
import java.io.*;

public class Main{
  static int[] map;
  static int n;

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    // 한칸밖에 없다면 그냥 그 자체로 도착한 셈 
    if( n == 1 ){
      System.out.println(0);
      return;
    }
    map = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 0 ; i < n ; i++){
      map[i] = Integer.parseInt(st.nextToken());
    }
    int[] d = new int[n];
    // 방문하지 않았던 곳은 -1로 초기화 (첫번째 자리는 제외 - d[0] = 0)
    for(int i = 1 ; i < n ; i++ ){
      d[i] = -1;
    }
		
    // map[i] 부터 시작해서 점프점프를 해주자
    for(int i = 0 ; i < n ; i++ ){
      // 만약 한번도 과거에서 점프로 온 적이 없는 곳이라면 여기서 출발하는 자체가 불가능
      if(d[i] == -1){
        continue;
      }
      // 최대 map[i] 값까지 갈 수 있다 
      for(int j = 1 ; j <= map[i] ; j++){
        if(i+j < n){
          if(d[i+j] == -1){ // 만약 갈 곳이 한번도 방문된적 없다면
            d[i+j] = d[i]+1; // 그냥 그대로 점프 뿅 
          }else{ // 만약 이 전에 방문한 적이 있다면 
            d[i+j] = Math.min(d[i+j], d[i] + 1); // 현재값보다 작다면 교체
          }

        }
      }
    }
      System.out.println(res);
  }
}