C++에서 주어진 조건에 따라 배열을 동일한 합 부분으로 나눕니다.

여기서 우리는 한 가지 문제를 보게 될 것입니다. 하나의 배열 arr가 주어졌다고 가정합니다. 배열이 다음과 같이 두 부분으로 분할될 수 있는지 확인해야 합니다.

• 두 하위 어레이의 하위는 동일합니다.
• 5의 배수인 모든 요소는 동일한 그룹에 속합니다.
• 3의 배수이지만 5의 배수가 아닌 모든 요소는 같은 그룹에 속합니다.
• 다른 모든 요소는 다른 그룹에 있습니다.

배열 요소가 {1, 4, 3}이라고 가정하면 {1, 3}의 합이 {4}의 합과 같고 그룹도 주어진 조건에 맞기 때문에 분할될 수 있습니다.

알고리즘

isSplitArray(arr, n, 시작, left_sum, right_sum) -

Begin
   if start = n, then return true when left_sum = right_sum, otherwise false
   if arr[start] is divisible by 5, then add arr[start] with the left_sum
   else if arr[start] is divisible by 3, then add arr[start] with the right_sum
   else
      return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start])
   isSplitArray(arr, n, start + 1, left_sum, right_sum)
End

예시

#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
   if (start == n) //when it reaches at the end
      return left_sum == right_sum;
   if (arr[start] % 5 == 0) //when the element is divisible by 5, add to left sum
      left_sum += arr[start];
   else if (arr[start] % 3 == 0) //when the element is divisible by 3 but not 5, add to right sum
         right_sum += arr[start];
   else // otherwise it can be added to any of the sub-arrays
         return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
   // For cases when element is multiple of 3 or 5.
   return isSplitArray(arr, n, start + 1, left_sum, right_sum);
}
int main() {
   int arr[] = {1, 4, 3};
   int n = sizeof(arr)/sizeof(arr[0]);
   if(isSplitArray(arr, n, 0, 0, 0)){
      cout <<"Can be split";
   } else {
      cout <<"Can not be split";
   }
}

출력

Can be split