C++에서 주어진 제약 조건이 있는 N*N 행렬의 최대 1 수

다음 제약 조건으로 이진 행렬에서 가능한 최대 1 수를 찾는 작업이 주어집니다.

X<=N인 경우 두 개의 정수 N 및 X가 제공됩니다. 이진 행렬의 크기는 N*N이어야 하고 크기 X*X의 모든 부분행렬은 최소한 하나의 0을 포함해야 합니다.

이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -

입력 - N=4, X=2

출력 − 12

설명 − 결과 행렬은 −

입력 - N=7, X=3

출력 − 45

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

1의 최대 수를 얻으려면 먼저 주어진 행렬에 필요한 최소 0 수를 찾아야 합니다.

모든 행렬에서 공통 패턴을 관찰하면 필요한 0의 수 =(N / X)²

따라서 최대 1 수 =행렬의 총 요소 수 – 0 수\
MaxOne() 함수에서 int 유형의 변수 Z를 만들고 (N / X)² 와 같은 필요한 최소 0 수를 저장합니다.
그런 다음 int 유형의 다른 변수 total =N*N을 초기화하여 행렬의 전체 크기를 저장합니다.
그런 다음 마지막으로 int as =total – Z를 초기화하여 최종 답변을 저장하고 as를 반환합니다.

예

#include <bits/stdc++.h>
using namespace std;
int MaxOne(int N, int X){
   // Minimum number of zeroes that are needed
   int Z = (N / X);
   Z = Z * Z;
   /* Totol elements in matrix = square of the size of the matrices*/
   int total =N * N;
   //Final answer
   int ans = total - Z;
   return ans;
}
int main(){
   int N = 4;
   int X = 2;
   cout << MaxOne(N, X);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 -