[백준] 11060 점프 점프 - 동적계획법(Dynamic Programming, DP) JAVA

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

11060번: 점프 점프

코드설명

DP 문제입니다.

 

이 문제의 핵심은 

i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 

를 구현하는 것입니다.

 

DP는 각 index에 도착할때까지의 최소 점프값을 의미합니다.

일반적으로 이러한 문제는

1. 도착지점에서 해당 지점에 도착할 수 있는 경우인지 체크하거나

2. 시작지점에서 해당 지점에 도착할 수 잇는 경우인지 체크하는 2가지 경우로 나뉩니다.

이번 문제는 시작점에서 Ai 이하만큼 오른쪽으로 떨어진 칸으로 모두 갈 수 있으므로 시작지점에서 진행합니다.

( 도착지점에서 해당 점에 도착할 수 있는 경우로 이를 구현하는 것보다는 시작점 기준으로 진행하는것이 수월합니다. )

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int T, N;
	public static int[] arr = new int[1001];
	public static int[] dp = new int[1001];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	Arrays.fill(dp, 1001);
    	dp[0] = 0;
    	for(int i=0; i<N;i++) {
    		int step = arr[i];
    		for(int j=i + step; j>i;j--) {
    			if( j < N) {
    				dp[j] = Math.min(dp[j], dp[i] + 1);
    			}
    		}
    	}
    	
    	if(dp[N-1] == 1001) {
    		System.out.println(-1);
    	}else {
    		System.out.println(dp[N-1]);	
    	}
    	
    }
}

 

재귀와 메모이제이션을 활용합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[] arr;
	static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		cache = new int[N];
		Arrays.fill(cache, -1);
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		answer = DFS(0);
		if(answer >= 1001) {
			System.out.println(-1);
		}else {
			System.out.println(answer);
		}
		
	}
	static int DFS(int now) {
		if(now == N-1) {
			return 0;
		}
		if(arr[now] == 0 && now != N-1) return 1001;
		if(cache[now] != -1) return cache[now];
		
		int ret = 1001;
		for(int next = now + 1; next <= now + arr[now] && next < N; next++) {
			ret = Math.min(ret, DFS(next) + 1);
		}
		
		return cache[now] = ret;
	}
	
}