행 x 열 행렬이 입력으로 주어집니다. 목표는 그 부분행렬의 요소들의 합이 정수 k로 나누어질 수 있도록 행렬[row][col] 내의 모든 부분행렬을 찾는 것입니다.
행렬이 mat[3][3]이고 k가 4이면 부분행렬은 다음과 같습니다.-
예를 들어 이해합시다.
예를 들어
입력 - 행렬[3][3] ={ {1,1,1}, {2,2,2}, {3,3,3} } k=4
출력 - 합이 'k'인 부분행렬의 개수는 다음과 같습니다. 4
설명 - 부분행렬은 위와 같을 것입니다.
입력 - 행렬[3][3] ={ {1,1,1}, {2,2,2}, {3,3,3} } k=12
출력 - 합이 'k'인 부분행렬의 개수는 다음과 같습니다. 4
설명 - 하위 행렬은 아래와 같이 표시됩니다.-
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 행렬을 왼쪽에서 오른쪽으로 순회하고 왼쪽 및 오른쪽 열의 각 쌍에 대해 배열 arr[]에 부분 행렬의 요소를 추가하고 k로 나눌 수 있는 합을 갖는 요소와 부분 배열의 합을 별도로 계산합니다.
check_val() 함수는 부분행렬의 요소가 있는 배열을 1D 배열로 취합니다. 이제 누적 합계를 계산하고 k로 나머지를 확인하고 나머지 빈도를 배열 arr_2[]에 저장합니다.
- 행렬[row][col]과 정수 k를 입력으로 받습니다.
- check_val(int arr[], int size, int k) 함수는 부분행렬의 요소 중 arr[]을 가져와 k로 나눌 수 있는 합계를 갖는 arr 내의 모든 부분 배열의 개수를 반환합니다.
- 변수 개수와 온도를 0으로 취합니다.
- k가 있는 누적 합계의 나머지 빈도를 저장하기 위해 배열 arr_2[]를 사용합니다.
- i=0에서 i
- for 루프 트래버스 주파수 배열 arr_2[]를 다시 사용하고 각 값에 대해 arr_2[i] * (arr_2[i] - 1)) / 2를 추가하여 가능한 모든 하위 배열의 수로 계산합니다.
- 끝에 rr_2[0]을 추가하여 계산합니다.
- 함수 matrix_divisible(int matrix[row][col], int size, int k)는 입력 부분행렬을 받아 k로 나눌 수 있는 합을 갖는 모든 부분행렬의 개수를 반환합니다.
- 초기 카운트를 0으로 합니다.
- 임시 배열 arr[크기]를 가져옵니다.
- 두 개의 for 루프를 사용하여 왼쪽 열 인덱스 i와 오른쪽 열 인덱스 j를 설정합니다.
- 요소의 합을 arr[temp]+=matrix[temp][j]로 계산합니다.
- arr[]의 하위 배열 수에 대해 check_val(arr, size, k)을 추가하여 계산합니다.
- 모든 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