C++로 배열을 합이 같은 두 부분 배열로 나눌 수 있는지 확인하는 방법

배열 A가 주어졌을 때, 이 배열을 두 부분으로 나누어 각 부분의 합이 서로 같아지도록 할 수 있는지 확인하는 문제입니다. 예를 들어 배열의 요소가 [6, 1, 3, 2, 5]라면, [6, 1]과 [2, 5]가 합이 같은 두 부분 배열이 될 수 있습니다.

해결 아이디어

이 문제는 다음 규칙에 따라 간단하게 해결할 수 있습니다.

1. 먼저 배열의 모든 요소를 더해 전체 합(total_sum)을 구합니다.
2. 배열의 각 요소를 순서대로 순회하면서 지금까지의 누적합(so_far_sum)을 관리합니다.
3. 각 위치에서 2 × so_far_sum + arr[i] == total_sum 조건을 검사합니다. 이 조건이 성립하면 현재 요소를 기준으로 왼쪽 부분의 합과 오른쪽 부분의 합이 같다는 의미입니다.

여기서 오른쪽 부분의 합은 전체 합에서 왼쪽 누적합과 현재 요소를 뺀 값, 즉 total_sum − so_far_sum − arr[i]로 계산됩니다. 이 값이 왼쪽 누적합과 같아지는 분할 지점을 찾는 것이 핵심이며, 조건을 만족하는 지점이 없다면 배열을 나눌 수 없습니다.

C++ 구현 예제

#include<iostream>
#include<numeric>
using namespace std;
void displaySubArray(int arr[], int left, int right) {
    cout << "[ ";
    for (int i = left; i <= right; i++)
        cout << arr[i] << " ";
        cout << "] ";
    }
    void subarrayOfSameSum(int arr[] , int n) {
        int total_sum = accumulate(arr, arr+n, 0);
        int so_far_sum = 0;
        for(int i = 0; i<n; i++){
            if(2*so_far_sum+arr[i] == total_sum){
                cout << "subarray 1: "; displaySubArray(arr, 0, i-1);
                cout << "\nsubarray 2: "; displaySubArray(arr, i+1, n-1);
                    return;
            }
            so_far_sum += arr[i];
        }
    cout << "No subarray can be formed";
}
int main() {
    int arr[] = {6, 1, 3, 2, 5} ;
    int n = sizeof(arr)/sizeof(arr[0]);
    subarrayOfSameSum(arr, n);
}

실행 결과

subarray 1: [ 6 1 ]
subarray 2: [ 2 5 ]

복잡도 분석

배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 또한 이 방법은 배열에 음수가 포함된 경우에도 동일하게 동작하므로 다양한 입력에 활용할 수 있습니다.