[백준] 11060번 : 점프 점프 – JAVA [자바]

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

11060번: 점프 점프

 

---

• 문제

 

---

• 문제 풀이

백준 11060번 점프 점프는 DP를 이용해서 푸는 실버 2 난이도의 백준 문제이다. DP를 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

이 문제에서는 미로 가장 왼쪽에서 미로 가장 오른쪽으로 가는데 최소 몇 번의 점프를 해야 되는지 구해야 하는 문제이다. 최소 횟수를 구해야 하니 Math.min() 함수를 쓰는 것은 당연하다.

 

문제에 나와 있는 예제를 예시로 한번 보겠다.

 

우선 입력으로 들어오는 Ai 값들을 받아서 int형 배열 arr에 저장한다. 저장하면 다음과 같다.

그리고 long형 배열 dp를 만든다. dp를 초기화할 때 모든 값들을 일단 Integer.MAX_VALUE로 설정해둔다. 왜냐하면 최소 횟수를 구해야 되니 Math.min() 함수를 써야 되는데 값들이 0이면 비교하기가 곤란해진다. 

그리고 맨 왼쪽에서부터 시작해서 Bottom-up 방식으로 문제를 접근해야 한다. 현재 인덱스를 i라고 하겠다. arr [i]에 있는 값 이하만큼 움직일 수 있으니 다음과 같이 쓸 수 있다.

for (int j = 1; j <= arr[i]; j++) {
    dp[i+j] = Math.min(dp[i+j], dp[i]+1);
}

 

이렇게 모든 값들을 확인해서 마지막에 dp [n]만 출력해주면 된다.

 

 

---

• 코드

 

import java.util.*;
import java.io.*;
public class Main {
    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]);
        }
    }
}

 

---

• 후기

이번 문제는 조금 많이 틀렸던 거 같다. 이 문제는 반레들도 조금 있는 거 같고 boundary도 잘 체크해줘야 되는 문제이다.

 

나는 보통 문제를 풀기 전에 백준 문제 밑에 써져 있는 알고리즘 분류를 보는데 그래프 이론과 너비 우선 탐색이 있는 것을 봤을 때 이 문제를 꼭 너비 우선 탐색을 써서 풀어야 되나?라는 생각이 들었다. 나는 다른 풀이 방법이 생각나서 그냥 이중 for-loop으로 문제를 풀었지만 이중 for-loop 대신 queue를 써도 똑같이 풀 수 있는 문제인 거 같다.