有効な方法で要素をペイントするために色をカウントするC++コード

n個の要素を持つ配列Aがあるとします。 -

• 色を考慮する場合、この色のすべての要素は、同じ色の最小要素で割り切れる必要があります。

• 使用する色の数を最小限に抑える必要があります。

与えられたすべての数字を有効な方法でペイントするには、最小の色数を見つける必要があります。

したがって、入力がA =[10、2、3、5、4、2]の場合、出力は3になります。これは、最初の色を要素A[0]とA[3]にペイントし、2番目の色をペイントするためです。要素A[2]に追加し、残りの3つの要素に3番目の色をペイントします。

ステップ

これを解決するには、次の手順に従います-

n := size of A
ans := 0
sort the array A
for initialize i := 0, when i < n, update (increase i by 1), do:
   ok := 1
   for initialize j := 0, when j < i, update (increase j by 1),
do:
      ok := ok AND (1 if A[i] mod A[j] is not 0, otherwise 0)
   ans := ans + ok
return ans

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A)
{
   int n = A.size();
   int ans = 0;
   sort(A.begin(), A.end());
   for (int i = 0; i < n; i++)
   {
      int ok = 1;
      for (int j = 0; j < i; j++)
      ok &= (A[i] % A[j] != 0);
      ans += ok;
   }
   return ans;
}
int main()
{
   vector<int> A = { 10, 2, 3, 5, 4, 2 };
   cout << solve(A) << endl;
}

入力

{ 10, 2, 3, 5, 4, 2 }

出力

3