C++로 합이 k로 나누어 떨어지는 부분 행렬 개수 세기

행(row) × 열(col) 크기의 행렬이 입력으로 주어졌을 때, 행렬 내부에서 구성 요소들의 합이 정수 k로 나누어 떨어지는 모든 부분 행렬(submatrix)을 찾아야 합니다.

예를 들어 3×3 행렬 mat[3][3]과 k = 4가 주어진다면, 조건을 만족하는 부분 행렬들은 아래와 같이 나타낼 수 있습니다.

예제로 이해하기

입력 - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} }, k = 4

출력 - 합이 'k'로 나누어 떨어지는 부분 행렬의 개수: 4

설명 - 위에서 언급한 것처럼 해당 부분 행렬들이 형성됩니다.

입력 - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} }, k = 12

출력 - 합이 'k'로 나누어 떨어지는 부분 행렬의 개수: 4

설명 - 이번에도 동일하게 4개의 부분 행렬이 조건을 만족합니다.

프로그램에 적용된 접근 방식

이 접근 방식은 행렬을 왼쪽에서 오른쪽으로 순회하면서, 각 왼쪽·오른쪽 열 쌍에 대해 부분 행렬의 요소들을 1차원 배열 arr[]에 누적하여 더합니다. 그런 다음 해당 배열 안에서 합이 k로 나누어 떨어지는 하위 배열(subarray)의 개수를 별도로 계산합니다.

check_val() 함수는 부분 행렬의 요소들을 1차원 배열 형태로 받아 처리합니다. 먼저 누적합(cumulative sum)을 계산하고, 이를 k로 나눈 나머지를 확인한 뒤 각 나머지의 출현 빈도를 배열 arr_2[]에 저장합니다.

행렬 matrix[row][col]과 정수 k를 입력으로 받습니다.
check_val(int arr[], int size, int k) 함수는 부분 행렬의 요소들이 담긴 arr[]를 받아, 그 안에서 합이 k로 나누어 떨어지는 모든 하위 배열의 개수를 반환합니다.
count와 temp 변수를 0으로 초기화합니다.
누적합을 k로 나눈 나머지의 빈도를 저장할 배열 arr_2[]를 준비합니다.
i = 0부터 i < size까지 for 루프를 돌며 누적합을 계산합니다. 각 arr[i]를 temp에 더한 뒤, arr_2[((temp % k) + k) % k]++ 로 나머지 빈도를 증가시킵니다(음수 합 처리를 위해 mod 연산을 두 번 수행).
다시 for 루프로 빈도 배열 arr_2[]를 순회하면서, 값이 1보다 큰 경우 (arr_2[i] * (arr_2[i] - 1)) / 2를 count에 더해 만들 수 있는 모든 하위 배열의 개수를 구합니다.
마지막으로 arr_2[0]을 count에 더합니다.
matrix_divisible(int matrix[row][col], int size, int k) 함수는 입력 행렬을 받아 합이 k로 나누어 떨어지는 모든 부분 행렬의 총 개수를 반환합니다.
초기 count 값을 0으로 설정합니다.
임시 배열 arr[size]를 준비합니다.
두 개의 for 루프를 사용해 왼쪽 열 인덱스 i와 오른쪽 열 인덱스 j를 지정합니다.
arr[temp] += matrix[temp][j] 연산으로 요소들의 합을 누적합니다.
arr[] 내부의 하위 배열 개수를 반영하기 위해 check_val(arr, size, k)의 반환값을 count에 더합니다.
모든 for 루프가 종료되면 count를 결과로 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
#define row 10
#define col 10

int check_val(int arr[], int size, int k) {
    int count = 0;
    int temp = 0;
    int arr_2[k];
    memset(arr_2, 0, sizeof(arr_2));

    for (int i = 0; i < size; i++) {
        temp = temp + arr[i];
        arr_2[((temp % k) + k) % k]++;
    }
    for (int i = 0; i < k; i++) {
        if (arr_2[i] > 1) {
            count += (arr_2[i] * (arr_2[i] - 1)) / 2;
        }
    }
    count = count + arr_2[0];
    return count;
}

int matrix_divisible(int matrix[row][col], int size, int k) {
    int count = 0;
    int arr[size];

    for (int i = 0; i < size; i++) {
        memset(arr, 0, sizeof(arr));
        for (int j = i; j < size; j++) {
            for (int temp = 0; temp < size; ++temp) {
                arr[temp] += matrix[temp][j];
            }
            count = count + check_val(arr, size, k);
        }
    }
    return count;
}
int main() {
    int matrix[row][col] = {{2,4,-1},{6,1,-9},{2,2, 1}};
    int size = 3, k = 4;
    cout << "Count of sub-matrices having sum divisible ‘k’ are: " << matrix_divisible(matrix, size, k);
    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

Count of sub-matrices having sum divisible 'k' are: 7