버린 후 카드의 최소 합계를 얻는 C++ 코드

<시간/>

배열 T에 5개의 숫자가 있다고 가정합니다. 5개의 카드가 있고 각 카드에 숫자가 기록되어 있습니다. i번째 카드에는 T[i]가 적혀 있습니다. 우리는 일부 카드를 버릴 수 있으며 우리의 목표는 나머지 숫자에 쓰여진 숫자의 합을 최소화하는 것입니다. 그는 같은 번호의 카드를 최대 한 번에 2~3장 버릴 수 있습니다. 같은 번호의 카드 2~3장을 고를 수 없는 경우에는 카드를 버리지 않습니다. 가능한 최소 금액을 찾아야 합니다.

따라서 입력이 T =[7, 3, 7, 3, 20]과 같으면 숫자가 7인 두 개의 카드를 제거하기 때문에 출력은 26이 됩니다. 나머지 합계는 3 + 3 + 20 =26이 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := 5
m := 0
Define an array k of size: 101 and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   a := T[i]
   m := m + a
   (increase k[a] by 1)
M := m
for initialize i := 0, when i < 101, update (increase i by 1), do:
   if k[i] > 1, then:
      M := minimum of M and (m - i * (minimum of 3 and k[i]))
return M

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> T)
{
   int n = 5, m = 0, a;
   int k[101] = { 0 };
   for (int i = 0; i < n; i++)
   {
      int a = T[i];
      m += a;
      k[a]++;
   }
   int M = m;
   for (int i = 0; i < 101; i++)
      if (k[i] > 1)
      {
         M = min(M, m - i * (min(3, k[i])));
      }
   return M;
}
int main()
{
   vector<int> T = { 7, 3, 7, 3, 20 };
   cout << solve(T) << endl;
}

입력

{ 7, 3, 7, 3, 20 }