[LeetCode] 1975. Maximum Matrix Sum

https://leetcode.com/problems/maximum-matrix-sum/description/

leetcode - Maximum Matrix Sum

문제 유형: 행렬, 그리디

문제 난이도: Medium

 

문제

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 x n의 정방행렬 matrix를 받습니다. 당신은 이 연산을 몇 번이고 할 수 있습니다:

- 두 인접한 요소를 골라서 각각 -1씩 곱하기

연산을 적용한 뒤, 최대 총합을 구하시오.

 

풀이

여러워 보이지만, 간단하다.

음수의 개수가 홀수 개라면, 연산 이후 1개만 남길 수 있다. 아무리 뒤집어보고 볶아봐도 0개를 만들 수는 없고, 반드시 하나가 남는다.

짝수 개라면, 모두 양수로 만들 수 있다.

 

즉, 행렬의 각 요소의 절대값을 더하고, 음수의 개수가 홀수개라면, 가장 작은 절대값 * 2를 뺀다.

가장 작은 절대값의 수를 음수로 하기로 한 것이다.

이미한번 더해져있으니 두 번빼야 한 번 뺀 것이다.

그러나, 0에도 적용가능하니, 가장 작은 절대값에는 0도 가능하다!

 

 

코드

C++

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        int minusCount = 0;
        int minabs = INT_MAX;
        long long ans = 0;  
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                ans += abs(matrix[i][j]);
                if(matrix[i][j] < 0) {
                    minusCount++;
                }
                minabs = min(abs(matrix[i][j]), minabs);
            }
        }

        if(minusCount % 2 == 1) ans -= 2*minabs;
        return ans;
    }
};