C++의 최대 개수

모든 셀의 값이 0 또는 1이고 크기가 l x l인 M의 정사각형 부분행렬이 최대 maxOnes개의 1을 갖도록 차원이 w x h인 행렬 M이 있다고 가정합니다. 행렬 M이 가질 수 있는 최대 가능한 개수를 찾아야 합니다.

따라서 입력이 w =3, h =3, l =2, maxOnes =1과 같으면 출력은 3*3 행렬에서와 같이 4가 됩니다. 2*2 부분 행렬은 1개 이상을 가질 수 없습니다. . 4개가 있는 가장 좋은 솔루션은 -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0

• 크기가 n x n인 하나의 2D 배열 sq를 만듭니다.

• initialize i :=0의 경우 i <높이일 때 업데이트(i를 1만큼 증가), −

  • j 초기화의 경우:=0, j <너비일 때 업데이트(j를 1만큼 증가), 수행 -

    • sq[i mod n, j mod n] 1 증가

• 배열 정의 v

• initialize i :=0의 경우, i

  • j 초기화의 경우:=0, j

    • v

      끝에 sq[i, j] 삽입

• 배열 v를 역순으로 정렬

• initialize i :=0, j :=0, i

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
      int ret = 0;
      vector < vector <int> > sq(n, vector <int>(n));
      for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
            sq[i % n][j % n]++;
         }
      }
      vector <int> v;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n ; j++){
            v.push_back(sq[i][j]);
         }
      }
      sort(v.rbegin(), v.rend());
      for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
         ret += v[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maximumNumberOfOnes(3,3,2,1));
}

입력

3, 3, 2, 1

출력

4