문제
1×N 크기의 미로에서 각 칸에 적힌 값 이하만큼 오른쪽으로 점프할 수 있을 때, 가장 왼쪽에서 가장 오른쪽까지 도달하기 위한 최소 점프 횟수를 구하라. 도달할 수 없으면 -1을 출력한다.
입력
첫째 줄에 N (1 이상 1,000 이하), 둘째 줄에 각 칸에 적힌 값이 주어진다.
출력
최소 점프 횟수를 출력한다. 도달할 수 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 1 2 0 1 3 2 1 5 4 2 | 5 |
풀이
1차원 DP로 각 위치까지의 최소 점프 횟수를 계산한다.
dp[i]를 i번째 칸까지의 최소 점프 횟수로 정의하고Integer.MAX_VALUE로 초기화한다dp[1] = 0으로 시작점을 설정한다- 각 위치 i에서 도달 불가능(
dp[i] >= MAX_VALUE)이면 건너뛴다 - 도달 가능한 위치 i에서 1~
arr[i]칸만큼 오른쪽 칸의dp[i+j]를min(dp[i+j], dp[i]+1)로 갱신한다 dp[n]이MAX_VALUE이상이면 -1, 아니면dp[n]을 출력한다
핵심 아이디어: 각 칸에서 도달 가능한 모든 칸을 갱신하는 전방 DP로, 도달 불가능한 칸에서는 전파를 중단한다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day288BOJ11060점프점프 {
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 + 1];
long[] dp = new long[1101];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
dp[i] = Integer.MAX_VALUE;
}
dp[1] = 0;
for (int i = 1; i <= n; i++) {
if (dp[i] >= Integer.MAX_VALUE)
continue;
for (int j = 1; j <= arr[i]; j++) {
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
}
if (dp[n] >= Integer.MAX_VALUE) {
System.out.print(-1);
} else {
System.out.print(dp[n]);
}
}
}복잡도
- 시간: O(N²)
- 공간: O(N)