백준 10653 마라톤2 // dp, 조합대신 점프 idea

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

* 시도1

완탐) 500 C 250 -> 건너뛸 체크포인트 고르기 -> 불가

 

* 풀이

dp(idx, cnt) : idx, 점프횟수  그때 최소비용

이때, OX 퀴즈로 하면 안된다.

nxt 후보들에대해 한번에 점프하는 식으로 완탐해야 구현이 쉬워진다.

idx==n-1이 기저사례임에 주의 (n아님)

정답코드

import java.util.*;

class Pair {
    int y;
    int x;

    Pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    // 인덱스 i, j개 를 스킵 했을때, 그때 최소거리
    static int dp[][] = new int[504][504];
    static int n,k;
    static ArrayList<Pair> v = new ArrayList<>();

    // 인덱스 idx, cnt개 를 스킵 했을때, 그때 최소거리
    static int dfs(int idx, int cnt){
        if(idx==n-1){
            return 0;
        }
        if(cnt > k) { // 스킵한 개수가 k를 초과하면 배제
            return Integer.MAX_VALUE;
        }

        if(dp[idx][cnt]!=Integer.MAX_VALUE) {
            return dp[idx][cnt];
        }

        int ret = Integer.MAX_VALUE;
        for(int nxt=idx+1;nxt<n;++nxt){
            int jumpCount = nxt - idx - 1; // 건너뛰는 체크포인트 개수
            if (cnt + jumpCount > k) {
                continue;   // k를 넘는 스킵은 시도하지 않는다
            }
            ret = Math.min(ret, dist(idx,nxt) + dfs(nxt, cnt + jumpCount));
        }
        return dp[idx][cnt] = ret;
    }

    static int dist(int idx1, int idx2) {
        return Math.abs(v.get(idx1).y - v.get(idx2).y) + Math.abs(v.get(idx1).x - v.get(idx2).x);
    }

    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        for(int i = 0; i < n; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            v.add(new Pair(y, x));
        }

        for(int i=0;i<n; i++) {
            for(int j=0; j<n; j++) {
                dp[i][j]=Integer.MAX_VALUE;
            }
        }
        System.out.println(dfs(0, 0));
    }
}

 

for문 안에서 nxt 범위체크필요한 이유

(리턴문에서 배제하면 안되는 이유 : 오버플로)

 

 

* 시간복잡도