Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 행렬 뒤집기 후 얻을 수 있는 최대 점수 구하기

각 원소가 0 또는 1로만 이루어진 2차원 행렬 A가 있다고 가정해 보겠습니다. 여기서 '이동(move)'이란 임의의 행 또는 열 하나를 선택하여 해당 행(또는 열)에 속한 모든 값을 뒤집는 연산을 의미합니다. 즉, 0은 1로, 1은 0으로 바꾸는 작업입니다.

원하는 만큼 이동을 수행한 뒤에는 행렬의 각 행이 하나의 이진수로 해석되며, 행렬의 점수는 이 숫자들의 총합이 됩니다. 따라서 우리의 목표는 가능한 한 가장 높은 점수를 찾는 것입니다.

예를 들어 입력이 다음과 같다면 −

0011
1010
1100

출력은 39가 됩니다. 적절히 뒤집기 연산을 수행하면 행렬은 다음과 같이 변합니다 −

1111
1001
1111

따라서 각 행의 값은 15 + 9 + 15 = 39가 됩니다.

풀이 접근 방법

이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 첫 번째 열(최상위 비트)은 항상 모든 행을 1로 만들 수 있으므로, 나머지 열에 대해서는 1의 개수가 더 많도록 열 단위로 판단하면 됩니다. 구체적인 단계는 다음과 같습니다 −

  • n := 행의 개수, m := 열의 개수로 설정합니다.

  • ret := n × 2^(m−1) 로 초기화합니다. 첫 번째 열은 항상 전부 1로 만들 수 있으므로, 모든 행이 최상위 비트를 가진다고 가정하는 것입니다.

  • j를 1부터 m−1까지 반복합니다.

    • cnt := 0 으로 초기화합니다.

    • i를 0부터 n−1까지 반복하며, A[i][j] == A[i][0] 인 경우 cnt를 1씩 증가시킵니다. (첫 번째 열과 값이 같으면 행 뒤집기를 통해 함께 1로 만들 수 있습니다.)

    • temp := 2^(m−j−1) × max(cnt, n−cnt) 를 계산합니다. cnt와 n−cnt 중 큰 값이 곧 해당 열에서 1로 만들 수 있는 최대 개수입니다.

    • ret := ret + temp 로 누적합니다.

  • 모든 열에 대한 계산이 끝나면 ret을 반환합니다.

다음 구현 예제를 통해 더 잘 이해해 보겠습니다 −

예제 코드

#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