[JAVA][BOJ][S2] 11060. 점프 점프

11060번: 점프 점프

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이

DP를 사용해서 풀 수 있는 간단한 문제다 최솟값을 구해야 하기 때문에 Arrays.fill을 사용해서 DP 배열에 Integer.MAX_VALUE를 채워 주었다

코드

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

public class S2_11060_점프점프 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        int[] A = new int[N+1];
        int[] DP = new int[N+1];
        
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
        	A[i] = Integer.parseInt(st.nextToken());
		}
        
        // 최솟값을 구해야 하기 때문에 DP 배열을 최댓값으로 채움
        Arrays.fill(DP, Integer.MAX_VALUE);
        // 첫 번째는 무조건 0부터 시작
        DP[1] = 0;
        
        for (int i = 1; i <= N; i++) {
        	// DP[i]가 최댓값이라면, 한 번도 방문한 적 없는 배열이라는 뜻이 된다 => 올 수 없음
        	if(DP[i] != Integer.MAX_VALUE) {
        		int jump = A[i];			// 점프할 수 있는 최대 칸 수
        		for (int j = 1; j <= jump; j++) {	// 1부터 최대 칸 수까지 전부 확인
        			// 만약 오른쪽 끝을 넘어가지 않았다면
        			//현재 점프(DP[i]+1)와 예전에 저장해 둔 점프 기록(DP[i+j]) 중 작은 것을 저장
				if(i + j <= N) DP[i+j] = Math.min(DP[i]+1, DP[i+j]);
			}
        	}
	}
        
        
        int ans = -1;					// 끝까지 갈 수 없다면 -1 출력
        if(DP[N] != Integer.MAX_VALUE) ans = DP[N];	// 끝까지 갔다면 DP[N](저장해 둔 최솟값) 출력
        
        System.out.println(ans);
    }

}

결과

 

#자바 #java #boj #백준 #알고리즘