[백준] 11060 - 점프 점프 (Java)

[백준] 11060 - 점프 점프 (Java)

문제

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

풀이/후기

dp로 푸는 것을 파악했고,

점화식도 혼자 잘 찾았다!
근데 여러 번 제출해도 자꾸 틀렸다고 나왔다..ㅠ

 

인덱스를 0부터 시작했는데, 이 부분을 고쳐주니 정답이 되었다.

0으로 시작하면 만약 입력값이 0부터 시작될 때 아예 움직일 수 없는 상태가 되기 때문이다!

코드

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

public class Main {
	
	static int N;
	

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(str.nextToken());
        
        int[] inp = new int[N+1];
        int[] dp = new int[N+1];
        
        str = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<N+1; i++) {
        	inp[i] = Integer.parseInt(str.nextToken());
        	dp[i] = Integer.MAX_VALUE;
        }
        
        dp[1] = 0;
        
        for (int i = 1; i < N+1; i++) {
        	if (dp[i] == Integer.MAX_VALUE) continue; 
        	for (int j = i + 1; j <= i + inp[i] && j < N+1; j++) {
        		dp[j] = Math.min(dp[j], dp[i] + 1);
        	}
        }
        
        int result = dp[N];
        if (result == Integer.MAX_VALUE) result = -1;
        
        System.out.println(result);
    }
    
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/blob/master/%EB%B0%B1%EC%A4%80/Silver/11060.%E2%80%85%EC%A0%90%ED%94%84%E2%80%85%EC%A0%90%ED%94%84/%EC%A0%90%ED%94%84%E2%80%85%EC%A0%90%ED%94%84.java

참고