[백준 11060] 점프 점프 - 자바(JAVA)

1. 문제

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

11060번: 점프 점프

 

2. 풀이

`DP`로 문제를 풀었습니다.
dp배열은 해당 칸까지 가는데 걸리는 최소 점프 횟수입니다.
만약에 data[3]=3이고 dp[3]=2라면
3번째 칸 까지 가는 최소 점프 횟수는 2번인데
3번째 칸에서 4, 5, 6칸을 갈 수 있는데 점프를 하니까 3번(dp[3]+1)만에 갈 수 있습니다.
최소면 갱신하고 아니라면 무시하면 됩니다.
이렇게 최솟값을 갱신하면서 dp[0]부터 dp[N-1]까지 차례대로 구해주었습니다.

 

DP외에도 BFS, DFS 등 다양한 풀이 방법이 있는 것 같은데 나중에 시간이 된다면 다른 알고리즘으로 다시 풀어봐야 겠습니다ㅎㅎ

3. 코드

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

public class BOJ11060 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		int N=Integer.parseInt(br.readLine());
		int[] data=new int[N];
		int[] dp=new int[N];

		String[] input=br.readLine().split(" ");

		for(int i=0;i<N;i++) {
			data[i]=Integer.parseInt(input[i]);
			dp[i]=Integer.MAX_VALUE;
		}

    		// 첫 번째 칸이 0이면 종료
		if(N>=1 && data[0]==0) {
			System.out.println(-1);
			return;
		}

		dp[0]=0;

		for(int i=0;i<N-1;i++) {
			if(data[i]==0||dp[i]==Integer.MAX_VALUE) { // 다음칸으로 점프할 수 없음 || 오는 길이 없음
				continue;
			}
			for(int j=1;j<=data[i];j++) { // 점프할 수 있는 만큼 가보자
				if(i+j>=N) break; // 인덱스 벗어나면 종료
				dp[i+j]=Math.min(dp[i+j], dp[i]+1);
			}
		}

		if(dp[N-1]==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(dp[N-1]);
		}
	}
}