C++에서 요소를 제거하기 위해 주어진 규칙으로 가능한 최소 배열 크기 찾기

이 문제에서 n개의 숫자와 정수 값 k의 배열이 주어집니다. 우리의 임무는 주어진 요소 제거 규칙에 따라 배열의 가능한 최소 크기를 찾는 것입니다.

문제 설명 - 배열의 요소 수를 최소화해야 합니다. 후속 삭제 작업을 사용하면 한 번에 제거할 수 있는 요소의 수는 3입니다. 3개의 요소가 주어진 두 가지 조건을 만족하면 제거가 가능합니다.

조건 1 − 세 개의 요소가 인접해야 합니다.>

조건 2 - 두 인접 요소 간의 차이는 k, 즉 arr[i + 1] =arr[i] + k 및 ​​arr[i+2] =arr[i+1] + k입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

{4, 6, 8, 4, 1, 5 }, k = 2

출력

3

설명

인덱스 0, 1, 2에 대해 하나의 삭제 작업이 가능합니다.

해결 방법

이 문제는 한 번의 삭제 작업이 완료된 후 볼 수 있는 간접 삭제 작업이 있을 수 있으므로 해결하기가 약간 까다롭습니다. 예를 들어 5, 6, 7에서 요소를 삭제합니다. 이 삭제 후 새 배열에는 삭제 조건을 충족하는 요소 3, 4, 5가 있을 수 있습니다. 하위 문제가 겹치는 이러한 유형의 문제는 동적 프로그래밍 방식을 사용하여 해결할 수 있습니다. 이를 위해 나중에 필요할 때 액세스할 수 있도록 하위 문제의 결과를 저장하는 DP[] 행렬을 유지합니다. 이것을 암기라고 합니다.

우리 솔루션의 작동을 설명하는 프로그램

예

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
   if (DP[start][end] != -1)
      return DP[start][end];
   if ( (end-start + 1) < 3)
      return end-start +1;
   int minSize = 1 + calcMinSize(arr, start+1, end, k);
   for (int i = start+1; i<=end-1; i++){
      for (int j = i+1; j <= end; j++ ){
         if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
            2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
            minSize = min(minSize, calcMinSize(arr, j+1, end, k));
         }
      }
   }
   return (DP[start][end] = minSize);
}
int main() {
   int arr[] = {4, 6, 8, 4, 1, 5 };
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   memset(DP, -1, sizeof(DP));
   cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
   return 0;
}

출력

The minimum possible size of the array after removal is 3