k로 나누어 떨어지는 합을 가진 부분 배열의 개수 구하기 (C++)

개요

이 글에서는 배열에서 합이 k로 나누어 떨어지는 부분 배열(subarray)의 개수를 구하는 알고리즘을 다룹니다. 배열과 정수 k가 주어졌을 때, 연속된 원소들의 합이 k로 나누어 떨어지는 모든 부분 배열의 개수를 세는 것이 목표입니다.

접근 방법: 누적 합과 나머지 연산 활용

모든 부분 배열을 하나씩 확인하는 브루트 포스 방식은 O(n²) 이상의 시간이 소요됩니다. 하지만 누적 합(prefix sum)과 나머지 연산을 활용하면 O(n + k) 시간 안에 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

배열을 순회하며 누적 합을 계산하고, 이를 k로 나눈 나머지를 기록합니다.
누적 합이 음수일 때도 올바르게 처리하기 위해 ((cumSum % k) + k) % k 공식을 사용해 항상 양수 나머지를 얻습니다.
두 지점의 누적 합 나머지가 서로 같다면, 그 사이에 있는 부분 배열의 합은 반드시 k로 나누어 떨어집니다.
따라서 같은 나머지가 m번 등장했다면, 만들 수 있는 쌍의 개수는 조합 공식 m × (m − 1) / 2로 계산합니다.
나머지가 처음부터 0인 경우(누적 합 자체가 k의 배수)는 그 자체로 조건을 만족하므로 결과에 별도로 더해줍니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 합이 k로 나누어 떨어지는 부분 배열 개수 세기
int count_subarray(int arr[], int n, int k){
    int mod[k];
    memset(mod, 0, sizeof(mod));
    int cumSum = 0;
    for (int i = 0; i < n; i++) {
        cumSum += arr[i];
        // 음수여도 양수 나머지를 얻도록 모듈러스 적용
        mod[((cumSum % k) + k) % k]++;
    }
    int result = 0;
    for (int i = 0; i < k; i++)
        if (mod[i] > 1)
            result += (mod[i] * (mod[i] - 1)) / 2;
    result += mod[0];
    return result;
}

int main(){
    int arr[] = { 4, 5, 0, -2, -3, 1 };
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << count_subarray(arr, n, k) << endl;

    int arr1[] = { 4, 5, 0, -12, -23, 1 };
    int k1 = 5;
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << count_subarray(arr1, n1, k1) << endl;
    return 0;
}

실행 결과

7
7

동작 설명

첫 번째 예제에서 배열 {4, 5, 0, -2, -3, 1}과 k = 5가 주어지면, 합이 5로 나누어 떨어지는 부분 배열은 다음 7개입니다.

[5]
[5, 0]
[0]
[0, -2, -3]
[-2, -3]
[5, 0, -2, -3]
[4, 5, 0, -2, -3, 1]

배열에 음수 원소가 포함되어 있어도 나머지 보정 공식 덕분에 정확한 개수를 구할 수 있다는 점이 이 알고리즘의 중요한 특징입니다.

마무리

이 알고리즘은 시간 복잡도 O(n + k), 공간 복잡도 O(k)로 매우 효율적입니다. 누적 합과 나머지 카운팅 기법은 "합이 특정 조건을 만족하는 부분 배열 찾기" 유형의 문제에서 널리 활용되므로, 코딩 테스트 대비를 위해 반드시 익혀두는 것이 좋습니다.