C++에서 합이 짝수인 부분 배열의 개수 구하기

문제 설명

N개의 원소로 구성된 배열 arr[]가 주어졌을 때, 합이 짝수인 부분 배열(subarray)의 개수를 구하는 것이 이번 문제의 목표입니다.

예제를 통해 문제를 이해해 보겠습니다.

입력

arr[] = {2, 1, 3, 4, 2, 5}

출력

11

설명

합이 짝수가 되는 부분 배열은 총 11개이며, 다음과 같습니다.

{2}, {4}, {2}, {1, 3}, {4, 2}, {2, 1, 3}, {1, 3, 4},
{2, 1, 3, 4}, {1, 3, 4, 2}, {3, 4, 2, 5}, {2, 1, 3, 4, 2}

풀이 1: 완전 탐색 (브루트 포스)

가장 직관적인 방법은 모든 부분 배열의 합을 직접 계산하는 것입니다. 시작 인덱스 i를 고정한 상태에서 끝 인덱스 j를 하나씩 늘려 가며 누적합을 구하고, 합이 짝수일 때마다 카운트를 증가시킵니다. 모든 경우를 확인한 후 카운트를 반환하면 되며, 시간 복잡도는 O(N²)입니다.

구현 예제

#include <iostream>
using namespace std;

int countEvenSumSubArray(int arr[], int n) {
    int evenSumCount = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum % 2 == 0)
                evenSumCount++;
        }
    }
    return evenSumCount;
}

int main() {
    int arr[] = {2, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "합이 짝수인 부분 배열의 개수: " << countEvenSumSubArray(arr, n);
    return 0;
}

실행 결과

합이 짝수인 부분 배열의 개수: 4

풀이 2: 누적합의 홀짝성 활용 (O(N))

배열의 크기가 크다면 누적합(prefix sum)의 홀짝성을 이용해 O(N) 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 부분 배열 arr[i..j]의 합은 prefix[j] − prefix[i−1]로 나타낼 수 있습니다.
• 두 수의 차가 짝수가 되려면 두 수의 홀짝성이 서로 같아야 합니다.
• 따라서 지금까지 등장한 누적합 중 짝수의 개수와 홀수의 개수만 추적하면 됩니다.

단, 빈 접두사(합이 0)도 짝수로 간주해야 하므로 짝수 누적합의 개수를 1로 초기화하는 점에 유의하세요.

#include <iostream>
using namespace std;

long long countEvenSumSubArray(int arr[], int n) {
    long long evenPrefix = 1; // 빈 접두사(합 0)는 짝수로 취급
    long long oddPrefix = 0;
    long long prefix = 0, result = 0;

    for (int i = 0; i < n; i++) {
        prefix += arr[i];
        if (prefix % 2 == 0) {
            result += evenPrefix++;
        } else {
            result += oddPrefix++;
        }
    }
    return result;
}

int main() {
    int arr[] = {2, 1, 3, 4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "합이 짝수인 부분 배열의 개수: " << countEvenSumSubArray(arr, n);
    return 0;
}

실행 결과

합이 짝수인 부분 배열의 개수: 11

정리

완전 탐색은 구현이 간단하지만 O(N²)의 시간이 소요되는 반면, 누적합의 홀짝성을 활용하면 O(N) 만에 답을 구할 수 있습니다. 입력 크기가 큰 경우에는 후자의 방법을 사용하는 것이 훨씬 효율적입니다.