백준11060번 문제

문제 : 점프 점프

문제 설명 :

배열의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 문제. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

코드 :

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_11060 {
    public  static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] =-1;
        }
        dp[0]=0;
        for(int i=0;i<N;i++){
            if(dp[i]==-1) continue;
            for(int j=1;j<=arr[i];j++){
                if(i+j<N){
                    if(dp[i+j]==-1 || dp[i+j]>dp[i]+1){
                        dp[i+j] =dp[i]+1;
                    }
                }
            }
        }
        System.out.println(dp[N-1]);

        /*int cnt =0;
        int i=0;
        while(i<N-1){
            int max =0;
            for(int j=1;j<arr[i]+1;j++){
                if(i+j<N && max < j+arr[i+j] && arr[i+j]!=0) max = j;
                if( i+j == N) break;
            }
            i = i+max;
            cnt ++;
            if( i == N) break;

        }
        System.out.println(cnt);*/ //여기까지가 내가 푼 풀이 맞데틀..
        
    }
}

문제 풀이:

밑에 사진처럼 처음 dp[0]을 0으로 설정하고, arr배열의 해당 데이터의 크기만큼 dp[]의 값들을 1씩 더해가면서 구한다.

참조 : https://lemonlemon.tistory.com/146