BOJ 26969 - Bribing Friends

BOJ 26969 - Bribing Friends

간만에 DP한테 뚜드리맞은 문제

---

Knapsack인것과 $x_i$ 로 정렬하여 항상 $x_i$ 가 작은것에 cone을 쓰는것이 최적임은 관찰했지만 거기서 막혀서 에디토리얼을 참고했다.

우리가 $M$ 개의 정답이 될 소를 안다고 하자.

이 소들에서는 $x_i$ 가 작은것에 cone을 쓰는것이 최적의 효율을 보이므로 최적이다.

$x_i$ 로 정렬하고

$dp[N][A+B]$ 를 정의한다.

$dp[i][j]=i$ 번 째 소를 볼 차례이고, 현재 남은 mooney와 cone의 합이 $j$ 일 때, 지금까지 얻은 $P$의 최대합

$dp$값을 모두 방문하지 않음으로 초기화하고 $dp[1][A+B]=0$ 으로만 초기화한다.

이제 순회하며 아직 방문하지 않은 상태면 넘기고 그렇지 않다면 현재 소를 얻을 수 있는지 판단하고 $i+1$의 상태들을 업데이트 해준다.

$j$ 가 있을 때, 현재 남은 mooney는 $\text{Min}(A, j)$ 이고 cone은 $\text{Max}(0, j - A)$ 이다.

$x_i$가 오름차순 정렬되어있으므로 무조건 cone을 먼저 쓰는것이 최적의 해를 구할 수 있고 현재 남은 cone으로만 현재 소를 친구로 만들 수 있다면

$dp[i+1] \left[j- \left\lfloor \dfrac{\text{cone}}{x_i} \right\rfloor \cdot \text{cone}\right]$ 을 업데이트 해줘야 한다.

현재 남은 cone으로만 현재 소를 친구를 만들 수 없다면 일단 모든 cone을 다 쓰고 mooney를 써서 친구로 만들 수 있는지 봐야 한다.

$\text{mooney} \ge c_i-\left\lfloor \dfrac{\text{cone}}{x_i} \right\rfloor$ 인지 확인한다음에 그렇다면

$dp[i+1]\left[ \text{mooney} -c_i+\left\lfloor \dfrac{\text{cone}}{x_i} \right\rfloor \right]$ 를 업데이트 해줌이 올바르다.

---

개념은 어렵지 않아도 구현이 개인적으로 잘 짜야돼서 까다롭다.

반복문 DP를 많이 연습하지 않으면 흔히 발생하는 현상인데 초기값은 어떻게 설정해야 할지 현재 상태를 기반으로 다음 상태를 먼저 업데이트 할지, 이전값들을 이용해서 현재값을 업데이트할 지 잘 결정해야 한다. 이 문제는 전자의 구현이 더 알맞다.

여기서 알맞음의 기준은 현재의 상태를 이용해서 다음 상태들의 값을 업데이트 해주는 것이 더 편한 경우이다.

const int MAX = 2000;  
int dp[MAX + 5][MAX * 2 + 5];  
  
struct F {  
   int p, c, x;  
};  
  
void solve() {  
   int N, A, B;  
   cin >> N >> A >> B;  
  
   vector<F> f(N + 1);  
  
   for (int i = 1; i <= N; i++) {  
      cin >> f[i].p >> f[i].c >> f[i].x;  
   }  
   sort(f.begin() + 1, f.end(), [&](auto &a, auto &b) { return a.x < b.x; });  
  
   memset(dp, -1, sizeof dp);  
   dp[1][A + B] = 0;  
   for (int i = 1; i <= N; i++) {  
      for (int j = 0; j <= A + B; j++) {  
         if (dp[i][j] == -1) continue;  
         dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);  
  
         int mooney = min(A, j);  
         int cone = max(0, j - A);  
         int cone_need = f[i].x * f[i].c;  
         if (cone >= cone_need) {  
            dp[i + 1][j - cone_need] = max(dp[i + 1][j - cone_need], dp[i][j] + f[i].p);  
         } else {  
            int mooney_need = f[i].c - cone / f[i].x;  
            if (mooney_need <= mooney) {  
               dp[i + 1][j - cone - mooney_need] = max(dp[i + 1][j - cone - mooney_need], dp[i][j] + f[i].p);  
            }  
         }  
      }  
   }  
   cout << *max_element(dp[N + 1], dp[N + 1] + A + B + 1);  
}