CF 864E Fire

문제 보기

출제자 해설

문제 요약

\(n\)개의 item 목록이 주어지는데, 각 item은 다음과 같은 값들을 가진다.

• \(t_i\): \(i\)번째 item을 구하는데 소요되는 시간
• \(d_i\): \(i\)번째 item의 가치가 유효한 시간, 즉 가치를 지켜내기 위해 구해내야만 하는 시간
• \(p_i\): \(i\)번째 item의 가치

item들을 어떤 순서로 어떤 것들을 구하는지에 따라 얻을 수 있는 가치의 총합이 달라진다. 이때 가능한 가장 큰 가치의 합을 구하는 문제다.

문제 풀이

가장 단순한 방법은 가능한 모든 경우를 따져보는 것이다. 모든 경우를 다 따져볼 경우 각각의 item을 구할지 말지를 정해야 하고, 해당 item들을 어떤 순서로 구해야 하는지 따져봐야 하므로 시간복잡도는 \(O(2^n \times n!)\)이다. 문제에서 주어진 최대 \(n\)의 크기를 고려하면 너무 느린 방법이다.

최적해가 어떤 형태를 가질지 고민해보면 더 좋은 알고리즘에 대한 힌트를 얻을 수 있다. 최적해가 아래와 같다고 해보자(여기서 \(p, q, r, s\)는 몇 번째 item인지를 나타낸다고 하자).

$$p, ..., q, r, ..., s$$

여기서 \(d_q \gt d_r\)라고 해보자, 즉 \(q\)번째 item의 가치가 유효한 시간이 \(r\)번째 item의 시간보다 더 긴 경우다. 이 경우 두 item의 순서를 바꾼다고 하더라도 가치의 합이 더 나빠지지 않음을 확인할 수 있다. 따라서 인접한 두 item들의 순서를 \(d_i\)값이 작은 item이 앞 쪽에 오도록 정렬하더라도 최적해를 구할 수 있다. 그러면 item들을 구하는 순서는 정해진다.

어떤 순서대로 item들을 골라야 하는지 정해지면 문제는 쉬워진다. 아래와 같이 부분 문제를 정의해보자.

dp[i][ct]: 현재 시간이 ct일 때, i ~ n번째 item에서 얻을 수 있는 최대 가치 합

 위와 같은 부분 문제는 i번째 item을 구하느냐 마느냐에 따라 최대 가치 합이 달라진다. 따라서 선택에 따라 전이되는 다음 부분 문제들과의 관계를 세우면 문제를 \(O(n \times T)\)(여기서 \(T\)는 부분 문제에서 가능한 최대 시간이다. 가능한 최대 \(t\)값에 \(n\)을 곱한 값이라 볼 수 있다)에 풀 수 있다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;
const int MAX_D = 2e3 + 50;

struct Item {
    int t, d, p, id;
    bool operator < (const Item& rhs) const {
        return d < rhs.d;
    }
};

int n;
Item items[MAX_N];
int dp[MAX_N][MAX_D];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &items[i].t, &items[i].d, &items[i].p);
        items[i].id = i + 1;
    }
    sort(items, items + n);
    for (int i = n - 1; i >= 0; i--) {
        for (int ct = 0; ct < MAX_D; ct++) {
            if (ct + items[i].t < items[i].d) {
                dp[i][ct] = max(dp[i][ct], dp[i+1][ct + items[i].t] + items[i].p);
            }
            dp[i][ct] = max(dp[i][ct], dp[i+1][ct]);
        }
    }
    vector<int> desired_set;
    int ct_temp = 0;
    for (int i = 0; i < n; i++) {
        if (ct_temp + items[i].t < items[i].d && dp[i][ct_temp] == dp[i+1][ct_temp + items[i].t] + items[i].p) {
            desired_set.push_back(items[i].id);
            ct_temp = ct_temp + items[i].t;
        }
    }
    printf("%d\n%d\n", dp[0][0], desired_set.size());
    for (int id : desired_set) {
        printf("%d ", id);
    }
    return 0;
}