BOJ 5550 - 헌책방

BOJ 5550 - 헌책방

• 동일한 장르에서 책들은 한 번에 파는것이 이득이다.
• 동일한 장르에서 비싼 책부터 파는것이 이득이다.

따라서 각 장르별 책들을 내림차순 정렬하면 $DP$를 돌릴 수 있다.

$dp[i][y]$를 $i$장르까지 봤을 때 $y$권을 팔았을 때 최댓값이라고 하고 풀면 된다.

$O(N^2)$ 에 풀 수 있다.

/*========================================================================================================

// 동일한 장르에서 책들은 한 번에 파는것이 이득이다.
// 동일한 장르에서 비싼 책부터 파는것이 이득이다.

========================================================================================================*/

void solve() {
   int n, k;
   cin >> n >> k;
   vvi G(11);
   for (int i = 0; i < n; i++) {
      int c, g;
      cin >> c >> g;
      G[g].pb(c);
   }
   for (int i = 1; i <= 10; i++) sort(all(G[i]), greater<>());

   // 장르 i까지 봤을 때 y권을 팔았을 때 최댓값
   vvi dp(11, vi(k + 1));

   int tot_book = 0;
   for (int i = 1; i <= 10; i++) {

      int sum = 0;
      for (int j = 0; j <= sz(G[i]); j++) {
         for (int y = j; y <= min(k, tot_book + j); y++) {
            maxa(dp[i][y], dp[i - 1][y - j] + sum + max(0ll, j - 1) * j);
         }
         if (j < sz(G[i]))
            sum += G[i][j];
      }
      tot_book += sz(G[i]);
   }
   cout << dp[10][k];
}