백준 22871 징검다리 건너기(large) java 자바 - jimoo

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

22871번: 징검다리 건너기 (large)

문제 풀이

다이나믹 프로그래밍으로 풀었다.

K의 최소값을 구하기위한 배열로 dp[n]를 선언해준다. (일단 dp[n] 배열의 각 값들을 -1로 초기화시켜준다.)

만약 dp의 값이 -1이 아닌경우는 저장된 값을 return 해준다.

-1인경우는 dp값을 Long.MAX_VALUE으로 변경해준다. 그리고 for문을 통해 모든 이동 범위의 힘(K)을 비교해준다.

최종적으로 jump함수의 리턴값이 K의 최솟값이된다.

**Long형을 쓴 이유**

 

자바에서 Integer.MAX_VALUE 값이 K가 가장 클 경우보다 작기때문이다.

=> K가 가장클 경우는 (1000000-1)*(1+|5000-2|) = 4,998,995,001

 

int형 값 범위(8 bits):  -2147483648 ~ 2,147,483,647

long형 값 범위(64 bits): -9223372036854775808 ~ 9,223,372,036,854,775,807

 

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

public class Main {
    static int n,k=0;
    static long[] arr, dp;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new long[n];
        dp = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i =0;i<n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            dp[i] = -1;
        }
        System.out.println(jump(0));

    }
    public static long jump(int x){
        if (x==n-1) return 0;
        if (dp[x] != -1) {
            return dp[x];
        }
        dp[x] = Long.MAX_VALUE;

        for(int i=x+1;i<n;i++){
            dp[x] = Math.min(dp[x], Math.max(go(i),(i-x)*(1+Math.abs(arr[x]-arr[i]))));
        }
        return dp[x];
    }
}