C++에서 행렬 뒤집기 후 점수

각 값이 0 또는 1인 2차원 행렬 A가 있다고 가정합니다. 여기에서 이동은 행이나 열을 선택하고 해당 행이나 열의 각 값을 토글하는 것으로 구성됩니다. 즉, 모든 0을 1로, 모든 1을 0으로 변경합니다. 이제 여러 번 이동한 후 이 행렬의 모든 행이 이진수로 해석되고 행렬의 점수는 이러한 숫자의 합입니다. 따라서 우리의 임무는 가능한 가장 높은 점수를 찾는 것입니다. 입력이 다음과 같은 경우 -

토글 후 행렬은 -

따라서 숫자는 15 + 9 + 15 =39입니다.

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

• n :=행 수 및 m :=열 수

• ret :=n x (2^(m – 1))

• 범위 1에서 m – 1까지의 j에 대해

  • cnt :=0

  • 0 ~ n – 1 범위의 i에 대해

    • cnt :=cnt + A[i, j] =A[i, 0]

  • temp :=2^(m – j – 1) * cnt 및 n – cnt의 최대값

  • ret :=ret + temp

• 리턴 렛

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int matrixScore(vector<vector<int>>& A) {
      int n = A.size();
      int m = A[0].size();
      int ret = (1 << (m - 1)) * n;
      for(int j = 1; j < m; j++){
         int cnt = 0;
         for(int i = 0; i < n; i++){
            cnt += (A[i][j] == A[i][0]);
         }
         int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt));
         ret += temp;
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
   Solution ob;
   cout << (ob.matrixScore(v));
}

입력

[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

출력

39