C++를 사용하여 배열의 모든 요소를 ​​삭제하는 데 필요한 최소 작업 수입니다.

문제 설명

정수 배열 arr이 주어지면 작업은 배열의 모든 요소를 ​​삭제하는 데 필요한 최소 작업 수를 인쇄하는 것입니다. 요소를 삭제하는 동안 제한이 적용됨 -

• 배열의 모든 요소는 무작위로 선택될 수 있으며, 배열로 나눌 수 있는 모든 요소는 배열에서 제거될 수 있습니다.

arr[] ={2, 4, 15, 10, 8, 5, 3}이면 모든 요소를 ​​삭제하려면 3번의 작업이 필요합니다. -

• 2를 선택하면 {2, 4, 10, 8}이 삭제됩니다.
• 5를 선택하면 {5, 15}가 제거됩니다.
• 3을 선택하면 {3}이(가) 제거됩니다.

알고리즘

1. Sort the array in ascending order and count number occurrence of each element
2. For each unmarked element starting from beginning mark all elements which are divisible by choose element, and increase the result counter

예시

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;
int getMinOperations(int *arr, int n){
   int map[MAX] = {0};
   sort(arr, arr + n);
   for (int i = 0; i < n; ++i) {
      map[arr[i]]++;
   }
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (map[arr[i]]) {
         for (int j = i; j < n; ++j) {
            if (arr[j] % arr[i] == 0) {
               map[arr[j]] = 0;
            }
         }
         ++cnt;
      }
   }
   return cnt;
}
int main(){
   int arr[] = {2, 4, 15, 10, 8, 5, 3};
   cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum required operations = 3