Leetcode 1975. Maximum Matrix Sum

문제

You are given an n x n integer matrix. You can do the following operation any number of times:

Choose any two adjacent elements of matrix and multiply each of them by -1.
Two elements are considered adjacent if and only if they share a border.

Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.

• n * n 의 matrix가 주어진다.
• 이 안에서 두개의 붙어있는 숫자를 찾아서 이들에게 전부 -1을 곱하는 연산을 할수 있다.
• 여러번 연산을 거친 이후 나올수 있는 matrix 값들의 최대 합을 구하여라

예시

• -3과 -2가 붙어있기에 이 둘에 -1을 곱하면 된다.
• 총 합 16

제한

• $n == matrix.length == matrix[i].length$
• $2 <= n <= 250$
• $-10^5 <= matrix[i][j] <= 10^5$

풀이

• 이 문제는 절대 그래프/BFS/DFS로 접근하는걸 권장하진 않을것 같다.
  ( 내입장에서 )
• 이 문제를 자세히 보면 이것을 찾을수 있다.
  • 마이너스가 되는 값은 최종적으로 0개/1개가 될것
• 이때 이 분기를 가르는 조건은 현재 마이너스가 짝수개 있냐, 홀수개 있냐이다.
• 반드시 2개의 숫자에 -1을 곱하기 때문에 홀수개의 마이너스값이 있으면 꼭 1개는 남아 있을 것이다.

그래서?

• 전체합, 가장 절댓값이 작은 수, 마이너스의 갯수를 구해서 적당히 리턴하면 된다.

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        minus_count = 0

        R = len(matrix)
        C = len(matrix[0])

        min_value = 10 ** 5 + 1
        value_sum = 0

        for r in range(R):
            for c in range(C):
                if matrix[r][c] < 0:
                    minus_count += 1

                min_value = min(min_value, abs(matrix[r][c]))

                value_sum += abs(matrix[r][c])

		# 마이너스의 수가 짝수일 경우 모든 수가 양수가 됨 -> 전체 절댓값 합 리턴
        if minus_count % 2 == 0:
            return value_sum
        # 마이너스의 수가 홀수인 경우 -> 전체 절댓값 합에서 가장 절댓값이 작은수 * 2 를 뺀다.
        else:
            return value_sum - min_value * 2

• 왜 min_value * 2를 빼냐?
  • 양수값 -> 음수값이 되는거니까 이만큼 차이가 남