Python에서 각 행 요소를 뒤집어 최대 합계를 찾는 프로그램

<시간/>

2D 이진 행렬이 있다고 가정합니다. 주어진 행렬의 모든 행이나 열에 대해 모든 비트를 뒤집을 수 있습니다. 이러한 연산을 얼마든지 수행할 수 있고 각 행을 이진수로 취급한다면 이 숫자로 만들 수 있는 가장 큰 합을 찾아야 합니다.

따라서 입력이 다음과 같으면

0	1	0
0	0	1

그러면 출력은 11이 됩니다. 두 행을 모두 뒤집은 것처럼 101과 110을 얻으면 합계는 5 + 6 =11입니다.

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

행렬 r에 대해 다음을 수행합니다.
- r[0]이 0과 같으면
  - 0에서 r까지의 범위에 있는 i에 대해 다음을 수행합니다.
    - r[i] :=-r[i] + 1
행렬의 열 크기에서 범위 1의 j에 대해
- cnt :=0
- 행렬의 행 수까지 범위 0에 있는 i에 대해 다음을 수행합니다.
  - cnt :=cnt + 행렬[i, j]가 1이면 1, 그렇지 않으면 -1
- cnt <0이면
  - 행렬 크기 범위 0에서 행렬의 i에 대해 다음을 수행합니다.
    - 행렬[i, j] :=-행렬[i, j] + 1
ans :=0
행렬 r에 대해 다음을 수행합니다.
- a :=0
- r의 각 v에 대해 다음을 수행합니다.
  - a :=2 * a + v
- ans :=ans + a
반환

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

예시

class Solution:
   def solve(self, matrix):
      for r in matrix:
         if r[0] == 0:
            for i in range(len(r)):
               r[i] = -r[i] + 1
      for j in range(1, len(matrix[0])):
         cnt = 0
         for i in range(len(matrix)):
            cnt += 1 if matrix[i][j] else -1
            if cnt < 0:
               for i in range(len(matrix)):
                  matrix[i][j] = -matrix[i][j] + 1
      ans = 0
      for r in matrix:
         a = 0
         for v in r:
            a = 2 * a + v
            ans += a
      return ans
ob = Solution()
matrix = [ [0, 1, 0], [0, 0, 1] ]
print(ob.solve(matrix))

입력

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