백준 26969, Bribing Friends

 

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

 

26969번: Bribing Friends

 

요약

 

A원과 B개의 아이스크림 콘을 갖고 있다. N명의 친구는 각각 $P_i$의 인기도, $C_i$의 비용, $X_i$의 할인율을 가진다. 주어진 A원과 B개의 콘으로 친구를 적절히 선택하여 최대의 인기도를 얻어보자.

 

---

1. DP를 떠올려볼 수 있다. 가장 나이브한 시간 복잡도는 다음과 같이 잡아볼 수 있을 것이다.
$dp[i][j][k]$ : i번째 친구까지 살펴보고, j원과 k개의 콘이 남았을 때의 최대 인기도.

각 친구마다 몇 개의 아이스크림 콘을 사용할 것인지 결정하여야 하므로 총 시간복잡도는 $O(NAB^2)$이다.

 

2. 그리디한 전략을 떠올려보자. 만약 데려갈 친구들이 정해져있다고 하면, 최대 할인율을 가지는 친구부터 가지고 있는 모든 아이스크림 콘을 사용하는 것이 최적이다. 친구들을 $X_i$가 작은 순으로 정렬하여 DP를 수행한다. 이제, 각 친구마다 몇 개의 아이스크림 콘을 사용할 것인지 결정할 필요가 없으므로 총 시간복잡도는 $O(NAB)$가 된다.

 

3. A와 B가 독립적인 변수인지 고민하여 보자.

정렬했을 때 더 앞쪽에 있는 친구들에게 최대한 모든 아이스크림 콘을 사용할 것이므로 사실 상태는 다음과 같이 두 가지로 나뉜다는 것을 알 수 있다.

 

1) A는 전혀 사용하지 않고 B만 사용하고 있는 상태
2) B를 이제 더이상 사용할 수 없고(앞으로 남은 친구의 모든 $X_i$ 값보다 B가 적어진 상태) A를 사용하는 경우.

따라서 시간 복잡도를 $O(N(A+B))$로 줄일 수 있다.

 

$dp[i][b][0]$ : i번째 친구까지 살펴보고, b개의 콘이 남았을 때의 최대 인기도

$dp[i][a][0]$ : i번째 친구까지 살펴보고, a원이 남았을 때의 최대 인기도

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;

struct cow {
    int X, P, C;

    bool operator<(const cow cmp) const {
        return X < cmp.X;
    }
};

int N, A, B;
cow arr[2005];
ll dp[2005][2005][2];

ll DP(int idx, int a, int t) {
    if (a < 0) return -INF;
    if (idx == N) return 0;
    ll &ret = dp[idx][a][t];
    if (ret != -1) return ret;
    ret = 0;

    ret = max(ret, DP(idx + 1, a, t));

    if (t == 0) {
        int d = min(arr[idx].C, a / arr[idx].X);
        if (d == arr[idx].C) ret = max(ret, arr[idx].P + DP(idx + 1, a - d * arr[idx].X, t));
        else ret = max(ret, arr[idx].P + DP(idx + 1, A - (arr[idx].C - d), 1));
    } else ret = max(ret, arr[idx].P + DP(idx + 1, a - arr[idx].C, t));

    return ret;
}

void solve() {
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++) cin >> arr[i].P >> arr[i].C >> arr[i].X;
    sort(arr, arr + N);

    memset(dp, -1, sizeof(dp));
    cout << DP(0, B, 0);
    return;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}