유효한 방식으로 요소를 칠하기 위해 색상을 계산하는 C++ 코드

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 다음과 같은 색상으로 요소를 페인트해야 합니다.

어떤 색상을 고려한다면 이 색상의 모든 요소는 같은 색상의 최소 요소로 나눌 수 있어야 합니다.
사용된 색상의 수를 최소화해야 합니다.

주어진 모든 숫자를 유효한 방식으로 칠하려면 최소 색상 수를 찾아야 합니다.

따라서 입력이 A =[10, 2, 3, 5, 4, 2]와 같으면 첫 번째 색상을 요소 A[0] 및 A[3]에 페인트하고 두 번째 색상을 페인트하기 때문에 출력은 3이 됩니다. 요소 A[2]에 추가하고 나머지 세 요소에 세 번째 색상을 페인트합니다.

단계

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

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 }