[백준] 11060번 점프 점프 문제 2가지 방법으로 풀어보기

www.acmicpc.net/problem/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을 출력한다.

---

위와 같은 문제는 두 가지 방법으로 풀어볼 수 있다. 

먼저 가장 직관적인 방법은 문제에서 요구하는 대로, 한 칸에서 이동할 수 있는 모든 칸으로 이동해보는 것이다. 문제에서 이동할 수 있는 칸을 배열 a에 받고, 점프 횟수를 배열 d에 저장한다면, i번째 위치에서 점프는 1부터 a[i]까지만큼 할 수 있는 것이다. 그래서 모든 경우에 배열을 -1로 초기화해놓고 최솟값이면 계속 update를 하는 식으로 구현을 해준다. 

 

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a = new int[n];
        int[] d = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            d[i] = -1;
        }
        d[0] = 0;
        for(int i=0; i<n-1; i++){
            if (d[i]==-1) continue;
            for(int j=1; j<=a[i]; j++){
                if (i+j<n){
                    if (d[i+j] == -1 || d[i+j] > d[i] + 1) {
                    d[i+j] = d[i] + 1;
                }
                }
            }
        }
          System.out.println(d[n-1]);
    }
}

---

반면에 역으로 푸는 방법도 존재한다. i 칸에 도착하기 전 배열의 위치를 j 칸이라고 생각했을 때 가장 멀리 칸을 뛸 수 있는 경우가 a[j]이기 때문에 i-j<=a[j]인 경우에 대해서 i보다 작은 배열의 index를 검사해보면 된다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] dist = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            dist[i] = -1;
        }
        dist[0] = 0;
        for (int i=1; i<n; i++) {
            for (int j=0; j<i; j++) {
                if (dist[j] != -1 && i-j <= a[j]) {
                    if (dist[i] == -1 || dist[i] > dist[j] + 1) {
                        dist[i] = dist[j] + 1;
                    }
                }
            }
        }
        System.out.println(dist[n-1]);
    }
}

 

---

이처럼 이러한 문제는 작은문제부터 큰 문제를 풀어나가는 방식이 있고, 큰 문제를 작은 문제로 바꾸어서 풀어나가는 방식 모두 다 가능하다. 문제에 따라서 더 편한 방식이 다르니 두 방법 모두 알아두면 편리할 것이다.