10653번 : 마라톤 2 [JAVA]

문제 링크

성공 여부(걸린 시간): 1차 시도-> 시간초과 (48분) 2차 시도-> 성공(18분)

아이디어

처음에는 범위도 그리 크지않고 BFS로 하면 되겠다~라고 생각하고 이런게 골드3? 이라 생각하며 풀었다.
그러나 처참히 실패했다. 사실 문제를 풀면서 연속으로 점프를 할 수 있다는 것을 생각하며 DP인가? 했으나
이미 코드를 다 짜버렸고 고치기 귀찮아서 그대로 완성했으나 시간초과가 떠버렸다.

문제의 BFS 코드의 시간복잡도

총 상태 개수:      O(NK)
상태당 점프 탐색:  O(N)
=> 전체 시간 복잡도: O(N²K)

최악의 경우에는
N ≤ 500, K ≤ N
O(N²K) = O(500² × 500) = 125,000,000 ≒ 1.25억 연산 이상이므로 제한시간 1초 초과함...

---

그럼 어떻게 해야할까
정답은 DP에 있었다.

이차원배열로 visited[포인트 위치][점프한 횟수]를 dp 배열을 만들어준다.
핵심 DP코드

        for(int i=0; i<N; i++){
            for(int j=0; j<=K; j++){//j는 뛴 횟수
                //뛸 수 있는 범위 만큼 전부 최신화 해줘야함
                for(int move=1; move+j-1<=K&&i+move<N; move++){//기본으로 1칸은 이동해야함
                    int gap = Math.abs(points[i][0]-points[i+move][0])+Math.abs(points[i][1]-points[i+move][1]);
                    visited[i+move][j+move-1] = Math.min(visited[i+move][j+move-1], visited[i][j]+gap);
                }
            }
        }

현재의 배열에서 뛸 수 있는 만큼 뛰어주며 뛰어서 도착한 dp배열에 현재값과 이동하는 거리를 합해서 비교해주고
최신화 해주면 되는 간단한 문제이다.

시간복잡도는 동일하게 O(N²K)이나 BFS와 비교했을때 상태를 관리하고 조건문 분기 등과 같은 오버헤드가 없기에
성공할 수 있다.

1차 시도 실패코드 -> BFS

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

public class Main {
    static int N, K;

    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());
        K = Integer.parseInt(st.nextToken());
        int [][] points = new int[N][2];
        int [][] visited = new int[N][K+1];
        ArrayDeque<int []> q = new ArrayDeque<>();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            points[i][0] = Integer.parseInt(st.nextToken());
            points[i][1] = Integer.parseInt(st.nextToken());
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        q.add(new int[]{0, 0, 0});//현재 포인트 위치, 거리, 건너뛴 횟수
        Arrays.fill(visited[0], 0);
        int result = Integer.MAX_VALUE;
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int curPoint = cur[0];
            int distance = cur[1];
            int jumped = cur[2];
            //System.out.println(curPoint+"지점, 걸린 거리: "+distance+" 점프 뛴 횟수"+jumped);
            if(curPoint==N-1){
                result = Math.min(result, distance);
                continue;
            }
            //건너뛰지 않은 경우
            int gap = Math.abs(points[curPoint][0]-points[curPoint+1][0])+Math.abs(points[curPoint][1]-points[curPoint+1][1]);
            if(visited[curPoint+1][jumped] > distance + gap){
                visited[curPoint+1][jumped] = distance + gap;
                q.add(new int[]{curPoint + 1, distance+gap, jumped});
            }
            //건너 뛴 경우
            if(jumped==K){
                continue;
            }
            for(int j = 2; j+jumped-1<=K && j+curPoint<N; j++){
                gap = Math.abs(points[curPoint][0]-points[curPoint+j][0])+Math.abs(points[curPoint][1]-points[curPoint+j][1]);
                if(visited[curPoint+j][jumped+j-1] > distance + gap){
                    visited[curPoint+j][jumped+j-1] = distance + gap;
                    q.add(new int[]{curPoint + j, distance+gap, jumped+j-1});
                }
            }
        }
        System.out.print(result);
    }
}

성공 코드(DP)

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

public class Main {
    static int N, K;

    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());
        K = Integer.parseInt(st.nextToken());
        int [][] points = new int[N][2];
        int [][] visited = new int[N][K+1];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            points[i][0] = Integer.parseInt(st.nextToken());
            points[i][1] = Integer.parseInt(st.nextToken());
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        int result = Integer.MAX_VALUE;
        Arrays.fill(visited[0], 0);
        for(int i=0; i<N; i++){
            for(int j=0; j<=K; j++){//j는 뛴 횟수
                //뛸 수 있는 범위 만큼 전부 최신화 해줘야함
                for(int move=1; move+j-1<=K&&i+move<N; move++){//기본으로 1칸은 이동해야함
                    int gap = Math.abs(points[i][0]-points[i+move][0])+Math.abs(points[i][1]-points[i+move][1]);
                    visited[i+move][j+move-1] = Math.min(visited[i+move][j+move-1], visited[i][j]+gap);
                }
            }
        }
        for (int x: visited[N-1]){
            result = Math.min(result, x);
        }
        System.out.print(result);
    }
}