이번 글에서는 흥미로운 배열 분할 문제를 살펴보겠습니다. 하나의 배열 arr가 주어졌을 때, 이 배열을 아래 조건을 모두 만족하는 두 부분으로 나눌 수 있는지 판단해야 합니다.
- 두 하위 배열의 합이 서로 같아야 합니다.
- 5의 배수인 모든 요소는 반드시 같은 그룹에 속해야 합니다.
- 3의 배수이면서 5의 배수가 아닌 모든 요소도 반드시 같은 그룹에 속해야 합니다.
- 그 외의 나머지 요소들은 어느 쪽 그룹에든 자유롭게 배치할 수 있습니다.
예를 들어 배열의 요소가 {1, 4, 3}이라고 가정해 보겠습니다. {1, 3}의 합이 {4}의 합과 동일하고, 3의 배수인 요소들이 같은 그룹에 있으므로 이 배열은 성공적으로 분할할 수 있습니다.
알고리즘
재귀 함수 isSplitArray(arr, n, start, left_sum, right_sum)를 사용하여 문제를 해결합니다. 로직은 다음과 같습니다.
시작
만약 start = n이라면, left_sum = right_sum일 때 true를 반환하고, 그렇지 않으면 false를 반환
만약 arr[start]가 5로 나누어떨어지면, arr[start]를 left_sum에 더함
그렇지 않고 arr[start]가 3으로 나누어떨어지면, arr[start]를 right_sum에 더함
그 외의 경우
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)
끝
C++ 구현 예제
핵심 아이디어는 5의 배수와 3의 배수는 미리 정해진 그룹에 강제로 배치하고, 나머지 요소들에 대해서만 왼쪽 또는 오른쪽 그룹에 넣는 두 가지 경우를 모두 탐색하는 것입니다.
#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
if (start == n) // 배열의 끝에 도달한 경우
return left_sum == right_sum;
if (arr[start] % 5 == 0) // 5로 나누어떨어지면 왼쪽 합에 추가
left_sum += arr[start];
else if (arr[start] % 3 == 0) // 5가 아닌 3의 배수라면 오른쪽 합에 추가
right_sum += arr[start];
else // 그 외에는 어느 쪽 그룹에도 배치 가능
return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
// 요소가 3 또는 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
배열 {1, 4, 3}의 경우 3의 배수인 3은 한쪽 그룹에 고정되고, 1과 4는 양쪽 그룹 중 하나에 배치될 수 있어 최종적으로 합이 같은 두 부분으로 나누는 것이 가능함을 확인할 수 있습니다.