백준 2651번 - 자동차경주대회 (Java)

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

 

그리디로 풀자니 이전의 값을 계속 다시 사용해야한다.

완전탐색을하면 2^100 승으로 당연히 시간초과다.

 

그래서 이 문제는 다이나믹 프로그래밍을 사용해야한다. DP 문제들은 다 그렇지만 1차원으로 해결가능한지? DP배열에 무슨 값을 넣어야하는지? 가 중요하다.

 

그리고 DP값에는 거의 모든 문제에서 정답이 들어간다는 것을 다시 한 번 명심하자.

 

즉, 

 

DP[N] = N 지점까지 최소 정비로 올 수 있는 경우가 된다.

 

정비를 받지 않고 한번에 오는 것이 당연히 시간적으로는 손해가 안난다.

 

4지점의 경우, 1,2,3 에서 4까지 올 수 있다. 그리고 1,2,3에서 4까지 올수 있는 경우의 수는 다음과 같다.

 

1. 정비를 받고 올 수 있음

2. 올 수 없음

 

우선 1, 2, 3 의 지점에 있다는 것은 반드시 그 곳에서 정비를 받는다는 뜻과 같기 때문에 정비를 받고 오는 것으로 DP를 갱신한다. 즉

 

DP[i] = MIN ( DP[i],  DP[j] + 정비시간 )

 

이렇게 이뤄지게된다. 만약 1, 2, 3 모두 4에 도달할 수 있는데 정비시간이 10 20 30 이라면 1에서 시간이 가장 짧으므로 10으로 갱신될 것이다.

 

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

class Main {
    static long[] dp = new long[105];
    static long[] log = new long[105];
    static ArrayList<Long> logArr = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long HP = Long.parseLong(br.readLine());
        long N = Long.parseLong(br.readLine());

        String[] arr = br.readLine().split(" ");

        HashMap<Long, Long> hm = new HashMap<>();
        hm.put(0L, 0L);
        ArrayList<Long> station = new ArrayList<>();
        station.add(0L);
        for (long i = 1; i <= N + 1; i++) {
            station.add(station.get((int) (i - 1)) + Long.parseLong(arr[(int) (i - 1)]));
            dp[(int) i] = Long.MAX_VALUE;
            log[(int) i] = 0L;
        }

        dp[0] = 0;

        String[] cost = br.readLine().split(" ");

        for (long i = 0; i < N; i++) {
            hm.put(i + 1, Long.parseLong(cost[(int) i]));
        }

        for (long i = 1; i < station.size(); i++) {
            for (long j = i - 1; j > -1; j--) {
                if (station.get((int) i) - station.get((int) j) > HP)
                    break;

                if (dp[(int) i] > dp[(int) j] + hm.get(j)) {
                    dp[(int) i] = dp[(int) j] + hm.get(j);
                    log[(int) i] = j;
                }
            }
        }

        System.out.println(dp[(int) (N + 1)]);
        printlog(N + 1);

        logArr.sort(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return Long.compare(o1, o2);
            }
        });

        System.out.println(logArr.size());

        for (Long i : logArr) System.out.print(i + " ");
    }

    static void printlog(long n) {
        if (log[(int) n] == 0) return;

        logArr.add(log[(int) n]);
        printlog(log[(int) n]);
    }
}