백준 24457 - 카페인 중독

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

아이디어

카페인이 낮은 걸 먼저 먹어야 한다.

 

왜냐하면 카페인이 작은 걸 먹어야 나중에 먹을 에너지 드링크의 손실을 최소화할 수 있기 때문이다.

 

그러면 카페인의 오름차순으로 정렬한 다음 동적 계획법으로 최적의 음료 선택을 계산해볼 수 있다.

DP

테이블은 다음으로 둔다.

 

dp(i, j) := i번째 음료를 먹을지 말지 결정하고 i번째부터 j개의 음료를 더 뽑을 수 있을 때 최대 지속시간

미래 카페인을 미리 계산하기

테이블을 짠 건 좋은데 카페인이 누적된만큼 효능이 손실된다는 조건을 고려해야 한다.

 

위에 테이블을 생각하면 j개의 음료를 뽑을 것이라고 고정한 상태기 때문에 우리는 누적 카페인 양을 미리 계산할 수 있다.

 

예를 들어 음료 1, 2를 먹었으면 다음에 먹을 음료의 에너지 손실은 음료 1, 2의 카페인 합산임을 당연히 알 수 있다.

 

역시 이렇게 음료 1, 2, 3을 먹었으면 다음에 먹을 음료의 에너지 손실은 음료 1, 2, 3의 카페인 합산만큼 된다.

 

또다시 음료를 한 개 먹은 상태고 최종적으로 a개를 먹을 계획이라면 나머지 a-1개의 음료에 대해 카페인 손실이 고정적으로 이미 먹은 음료만큼 들어옴을 알 수 있고 이 카페인이 c라고 할 때 손실의 총합은 c * (a - 1)이 된다.

 

즉, 테이블을 채울 때 음료를 마시기로 결정했다면 이전 값에다가 현재 드링크를 마실 때의 이득과 미래에 나머지 음료를 먹을 때 일어날 카페인 손실을 둘 다 더해주면 된다.

 

위 상황을 수식으로 표현하면 다음처럼 된다. (e는 에너지)

 

$e - c \times (a - 1)$

 

이렇게 접근하면 답이 음수가 될 수 있지 않나?라는 의문이 들 수 있는데 테이블을 다시 보자.

 

i번째부터 j개를 선택하는 것이다. 즉, 적당히 작은 j를 계산하면 음수가 아닌 해를 충분히 계산할 수 있다는 의미가 된다.

구현

이제 테이블을 계산해보도록 하자. 그런데 탑 다운으로 짜면 살펴보지 않는 상태가 생겨 모든 답을 계산할 수 없다. 바텀 업으로 계산 후 최댓값을 출력하도록 하자.

 

구현에 대해 잘 감이 오지 않으면 밑에 있는 코드를 참조한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
pii drink[5000];
ll dp[5001][5001];
 
void solve()
{
  cin >> n;
 
  for (int i = 0; i < n; i++) cin >> drink[i].first;
  for (int i = 0; i < n; i++) cin >> drink[i].second;
  sort(drink, drink + n, [](pii &l, pii &r) {return l.second < r.second;});
  for (int i = 1; i <= n; i++)
  {
    for (int j = n; j >= 0; j--)
    {
      dp[i][j] = max(dp[i - 1][j], dp[i][j]);
      if (j < n)
      {
        dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + drink[i - 1].first - (ll)j * drink[i - 1].second);
      }
    }
  }
 
  cout << *max_element(&dp[0][0], &dp[0][0] + 5001 * 5001);
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록