[백준 C++] 2651번 자동차경주대회

2651번: 자동차경주대회

문제 요약

문제

전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비소들은 출발지점에서 도착지점으로 가는 길가에 있으며 ①번부터 차례로 번호가 붙어 있다. 이 대회에서는 참가하는 선수의 안전을 위하여 정비를 받지 않고 미리 정한 거리를 초과하여 갈 수 없도록 규칙을 정하였다. 그리고 정비소마다 정비하는데 걸리는 정비 시간이 서로 다를 수 있다. 정비소에서 정비하는데 걸리는 시간을 가장 적게 하려고 할 때 최소 총 정비시간과 방문하는 정비소들을 구하는 프로그램을 작성하시오. 예를 들어, 아래 그림과 같이 정비소가 5개 있고, 한 번 정비를 받고 최대 140㎞를 갈 수 있는 경우를 생각해 보자. 출발지점에서 정비소 ①까지의 거리가 100㎞이고, 정비소 ①을 방문하여 정비할 때 걸리는 시간은 5분이다. 자동차가 출발지점에서 대회 규칙을 지키면서 정비소 ①, ③, ⑤를 차례대로 방문하여 도착지점까지 갈 수 있고, 정비소 ②, ④를 방문하여 갈 수도 있다. 정비소 ①, ③, ⑤를 방문하는 경우에는 16분(=5+4+7분)이 걸리는데, 이것은 정비소 ②, ④를 방문하여 걸리는 21분(=10+11분)보다 총 정비 시간이 적게 걸린다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에는 정비를 받지 않고 갈 수 있는 최대 거리가 주어진다. 둘째 줄에는 정비소의 개수가 입력되는데 정비소 수는 100개 이하이다. 셋째 줄에는 인접한 정비소 사이의 거리가 차례로 주어지는데 거리는 정비를 받지 않고 갈 수 있는 최대 거리보다 작거나 같고 모든 거리의 합은 $2^{31-1}$ 이하이다. 넷째 줄에는 정비소별 정비 시간이 차례로 주어지는데 모든 정비 시간의 합은 $2^{31-1}$ 이하이다. 모든 입력은 양의 정수이며 $2^{31-1}$ 이하이다.
• 출력: 첫째 줄에 정비소에서 정비하는데 걸리는 총 정비 시간을 출력한다. 둘째 줄에 방문하는 정비소의 개수를 출력한다. 셋째 줄에는 방문하는 정비소의 번호를 한 줄에 차례로 출력하며 정비소 번호 사이에 빈칸을 하나씩 넣는다. 정비소를 전혀 방문하지 않아도 되는 경우에 총 정비 시간은 0이고 정비소 번호는 출력하지 않는다. ``` 예제1

입력 140 5 100 30 100 40 50 60 5 10 4 11 7 출력 16 3 1 3 5

## 풀이
이 문제는 정비소를 적절히 들르면서 최소 비용으로 목적지까지 이동하는 경로를 구하는 DP 문제이다. 출발지에서 각 지점까지 도달하는 데 필요한 최소 비용과 경로를 저장하기 위해 dp 배열을 사용한다. dp[i]는 i번째 지점까지 도달하는 데 필요한 최소 비용과, 그때까지 들른 정비소의 번호를 담고 있는 구조체로 구성된다.
초기에는 출발 지점인 dp[0]만 비용 0, 경로는 빈 벡터로 초기화하고, 나머지 지점은 모두 도달할 수 없음을 의미하는 매우 큰 값으로 초기화한다. 이후 각 지점 i에 대해, 최대 주행 거리 maxd를 넘지 않는 선에서 다음 지점 j로 이동할 수 있는지를 확인하며 탐색한다. 이때 i+1부터 n+1까지 순차적으로 확인하면서 누적 거리 t를 갱신하고, t가 maxd를 초과하면 더 이상 진행하지 않는다.
만약 이동이 가능하고 dp[i]를 거쳐서 j에 도달하는 비용이 기존 dp[j]보다 작다면, dp[j]를 갱신한다. 이때 이전 경로 벡터를 복사한 뒤, 목적지가 아닌 경우에만 j를 경로에 추가한다. 이런 방식으로 모든 지점을 순회한 후, 최종 목적지인 n+1번 지점에 저장된 최소 비용과 경로를 출력하면 된다.

## 어려웠던 점
없다.

## 배운 점 / 느낀 점
없다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1e18
using namespace std;
struct ans{
    long long t;
    vector<int> j;
};

long long maxd, n;
vector<long long> jungbi;
vector<long long> times;
vector<ans> dp;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> maxd >> n;
    jungbi = vector<long long>(n+2);
    dp = vector<ans>(n+2, {(long long)INF, vector<int>()});
    times = vector<long long>(n+1);
    dp[0] = {0ll, {}};
    jungbi[n+1] = 0ll;
    for(int i = 0; i < n+1; i++){
        cin >> times[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> jungbi[i];
    }
    for(int i = 0; i <= n+1; i++){
        long long t = 0ll;
        for(int j = i+1; j <= n+1; j++){
            t += times[j-1];
            if(t > maxd){
                break;
            }
            if(dp[j].t > dp[i].t+jungbi[j]){
                dp[j].t = dp[i].t+jungbi[j];
                dp[j].j = dp[i].j;
                if(j != n+1)
                    dp[j].j.push_back(j);
            }
        }
    }
    cout << dp[n+1].t << '\n';
    cout << dp[n+1].j.size() << '\n';
    for(int i : dp[n+1].j){
        cout << i << ' ';
    }

    return 0;
}