C++에서 주어진 합계로 부분행렬 찾기

이 문제에서는 크기가 N*N인 2D 행렬과 두 개의 변수 sum과 size가 제공됩니다. 우리의 임무는 주어진 합으로 부분행렬을 찾는 것입니다. .

요소 합이 합과 같은 크기*크기의 부분행렬을 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : mat[][] = {
   {1, 5, 7, 9}
   {2, 4, 6, 8}
   {1, 2, 5, 6}
   {3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES

설명 -

The submatrix of size k with sum 22 is
{5, 7}
{4, 6}

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 가능한 모든 크기*크기 크기의 하위 배열을 만들고 합계를 찾은 다음 주어진 합계 값과 동일시하는 것입니다. 둘 다 같으면 반환합니다.

또 다른 접근 방식은 동적 프로그래밍 알고리즘 개념을 사용하는 것입니다. . 이 접근 방식에서 우리는 현재 인덱스 값까지 합계를 저장할 DP 배열을 만들 것입니다. 즉, DP[i][j]는 행 인덱스 0에서 i까지 및 열 인덱스 0에서 j까지 배열의 모든 요소의 합을 저장합니다. .

이 DP 배열을 사용하여 공식을 사용하여 두 시작 인덱스와 끝 인덱스 사이의 합계를 계산합니다.

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[ i_s][i_e]\:-\:DP[i_e][i_s]}$$

알고리즘

1단계 − (n+1)*(n+1) 크기의 DP 행렬을 만듭니다.

2단계 − 행렬의 각 요소에 대해 현재 인덱스까지의 합을 찾습니다.

3단계 − 0부터 n까지의 모든 인덱스에 대해 size*size 크기의 부분행렬의 합을 찾습니다. 수식을 사용하여 currSum에 저장합니다.

4단계 - currSum ==합계인 경우 true를 반환합니다.

5단계 - false를 반환합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

출력

Sub-Matrix of given size having the given sum is possible!