백준 22871번: 징검다리 건너기

백준 28771번: 징검다리 건너기

이분탐색 또는 dp로 풀 수 있는 문제다. 나는 이분탐색 연습중이라 이분탐색으로 풀었다!

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

public class Main {
    static int[] visit;
    static Boolean flag;
    static void checkRouteValid(long[] arr, int start, int N, long K){
        if(start==N-1){
            flag = true;
        }
        for(int j=start+1; j<N; j++){
            long result = (long)(j-start)*(1+Math.abs(arr[start]-arr[j]));
            if(result<=K && visit[j]==0){
                visit[j]=1;
                checkRouteValid(arr, j, N, K);
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N= Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        visit = new int[N];
        long left = 0;
        long right = (long)(N-1)*(1+Math.abs(arr[N-1]-arr[0]));
        long mid = 0;
        long ans = 0;
        while(left<=right){
            for(int i=0; i<N;i++){
                visit[i]=0;
            }
            visit[0]=1;
            flag=false;
            mid = (left+right)/2;
            checkRouteValid(arr,0,N,mid);
            if(flag){
                ans=mid;
                right=mid-1;
            }else{
                left=mid+1;
            }

        }
        System.out.println(ans);

    }


}

visit 설정해주지않으면 시간초과 나고, boolean 변환 형식은 틀리고 flag를 사용해서 경로여부탐색을 해야되는 것 같다. (모든 경우의 수를 다 탐색해야해서 그런듯?) 숫자의 범위가 1~1,000,000이라서 Long형식을 이용해줘야한다!
나는 이분탐색으로 풀었으니 dp 풀이도 한번 찾아봤다.

import sys
N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
INF = 1e9
dp=[INF for _ in range(N+1)]
dp[0]=0

for i in range(1,n):
	for j in range(0,i):
    	power = max((i-j)*(1+abs(arr[i]-arr[j])),dp[j])
        dp[i]=min(dp[i],power)
print(dp[n-1]

0에서 n-1까지의 인덱스값에 대하여, i(현재)값과 j(앞 인덱스)값 사이의 K값을 구하는데 돌을 건너는데 쓰는 힘의 값과 dp[j]중 큰것을 선택한다. (K값은 모든 루트중에서 가장 큰 힘의 값을 구하는 것이므로) 그리고 dp[i]는 dp[i]와 power중 작은 것을 선택한다. (dp는 INF로 초기화되어있고, 우리가 구하는 것은 K값 중 최소값이므로)
그래서 dp[n-1]을 구하면 정답이 된다.