BOJ 8903 - 장비

BOJ - 장비

처음에 $_5\mathrm{C}_k$ 같은 걸로 뭔가를 해보려고 했으나 실패했다.

해답

$k$가 작다는 것을 이용해서 풀 수 있다.

$k$개의 그룹을 나누는데, 모든 경우의 수를 따져보는 것이다.

$k=2$일 때, {1, 2}, {3,4,5} 처럼 나누거나 {3}, {1, 2, 4, 5} 처럼 나누는 것 등을 말한다.

이런식으로 하면 나뉘어진 그룹마다 $O(N)$ 으로 선택된 능력치의 종류들의 합이 가장 큰 것을 하나 뽑을 수 있는데, 각 그룹에 대해서 모두 뽑아온 것을 합쳐주면 된다.

어떤 $A$ 와 $B$ 그룹에서 각각 같은 것을 뽑아도 문제되지 않기때문에 특별히 처리해줄 필요가 없다.

void solve() {
   int n, k;
   cin >> n >> k;
   vvi arr(n, vi(5));
   fv2(arr);

   int ans = 0;
   if (k == 1) {
      for (int i = 0; i < n; i++) {
         ans = max(ll(ans), acc(arr[i]));
      }
   } else {
      k = min(k, 5);
      vvi group(5);
      function<void(int)> fn = [&](int cur) -> void {
         if (cur == 5) {
            int len = 0;
            for (int i = 0; i < 5; i++) len += sz(group[i]) > 0;
            if (len ^ k) return;
            int tot = 0;
            for (int g = 0; g < 5; g++) {
               if (!sz(group[g])) continue;
               int mx = 0;
               for (int i = 0; i < n; i++) {
                  int sum = 0;
                  for (int gi: group[g]) {
                     sum += arr[i][gi];
                  }
                  mx = max(mx, sum);
               }
               tot += mx;
            }
            ans = max(ans, tot);
            return;
         }
         for (int i = 0; i < 5; i++) {
            group[i].pb(cur);
            fn(cur + 1);
            group[i].pop_back();
         }
      };
      fn(0);
   }
   cout << ans << endl;
}