[백준] 11060번 점프 점프 (자바 풀이)

문제

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

11060번: 점프 점프

풀이

나는 이 문제를 그리디 알고리즘을 사용해서 풀었다. 

현재 점프할 수 있는 곳 중에서 그 칸에 도착했을 때 가장 멀리 갈 수 있는 곳으로 점프하면 가장 빠르게 도착할 수 있다.

현재 점프할 수 있는 곳 중에서 가장 멀리 점프한다는 뜻이 아니다!

 

예시를 보자. 아래와 같이 시작한다.

1 2 0 1 3 2 1 5 4 2
x

이 상황에서는 최대 한칸 밖에 못 가므로 그냥 한 칸을 뛴다.

1 2 0 1 3 2 1 5 4 2
  x

2칸을 뛸 수 있는데, 이때 0과 1중 1에 도착하면 더 멀리 갈 수 있다. 따라서 1로 뛴다.

1 2 0 1 3 2 1 5 4 2
        x

1칸을 뛸 수 있으므로 3으로 뛴다.

1 2 0 1 3 2 1 5 4 2
          x

3칸을 뛸 수 있는데, 이때 2, 1, 5 중 5에 도착하면 가장 멀리 갈 수 있다. 따라서 5로 뛴다.

1 2 0 1 3 2 1 5 4 2
                  x

마지막 칸에 도달할 수 있으므로 끝낸다.

 

그런데 내가 처음에 이 방법을 구현했을때 틀렸습니다를 받았었다. 이유가 뭘까하고 찾아보니 나는 단순히 뛸 수 있는 칸 중에서 가장 숫자가 큰 칸으로 뛰는 방식을 사용했는데, 이렇게 하면 틀리게 된다. 

 

예를 들어 아래와 같은 상황이 있다고 하자. 

3 3 1 2 1 2
x

3칸을 뛸 수 있는데, 이때 내가 구현한 방식은 3,1,2 중 3이 가장 크므로 3으로 뛰는 것이였다. 

만약 3으로 뛴다면

3 3 1 2 1 2
  x

3칸을 뛸 수 있으므로 1, 2, 1 까지 뛸 수 있다.

 

하지만 맨 처음칸에서 2가 있는 칸으로 뛴다면

3 3 1 2 1 2
        x

마지막 칸 까지 뛸 수 있으므로 더 멀리 갈 수 있다.

코드를 보면 더 쉽게 이해가능할 것이다.

---

나는 그리디 알고리즘을 사용했지만, 사실 DP를 사용하면 더 간단하게 해결 할 수 있다. 

이것은 코드를 보면 이해할 수 있을 것이다. 

코드

1. 그리디 알고리즘

import java.util.*;
import java.io.*;
 
public class Baekjoon_11060 {
    static int N;
    static int arr[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int idx = 1;
        int cnt = 0;
        boolean flag = false;
        while(idx < N) {
            int max = 0;
            int maxIdx = 0;
            /* 점프할 수 있는 칸 중 가장 멀리 갈 수 있는 곳으로 점프 */
            for(int i=idx+1; i <= idx+arr[idx]; i++) {
                if(i >= N) {
                    flag = true;
                    break;
                }
                
                if(max < i+arr[i]) {
                    max = i+arr[i];
                    maxIdx = i;
                }
            }
            
            /* 더 이상 점프를 못하면 -1 */
            if(arr[idx] == 0) {
                cnt = -1;
                break;
            }
            
            cnt++;
            idx = maxIdx;
            if(flag) break;
        }
        System.out.println(cnt);
    }
}

2. DP 알고리즘

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A;
    static int[] dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
 
        dp = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
 
        // if (A[1] != 0)
        dp[1] = 0;
 
        for (int i = 1; i <= N; i++) {
            if (dp[i] != Integer.MAX_VALUE) {
 
                int jump = A[i];
                for (int j = 1; j <= jump; j++) {
                    if (i + j > N)
                        continue;
 
                    dp[i + j] = Math.min(dp[i] + 1, dp[i + j]);
                }
            }
        }
 
        System.out.println(dp[N] == Integer.MAX_VALUE ? -1 : dp[N]);
    }
}

결과

1. 그리디 알고리즘

2. DP 알고리즘

시간 차이나 메모리 사용량에도 거의 차이가 없는 듯 하다. 하지만 구현 난이도는 DP가 더 쉬웠던 것 같다.