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

C++로 이진 행렬을 최대 K번 뒤집아 얻을 수 있는 최대 점수 구하기

문제 소개

이 문제에서는 0과 1로만 구성된 2차원 배열 arr[]와 정수 K가 주어집니다. 우리가 해야 할 일은 행렬의 행(row) 또는 열(column)을 최대 K번까지 뒤집는(flipping) 연산을 수행한 뒤, 각 행이 만들어내는 숫자들의 합이 최대가 되도록 하는 것입니다.

문제 설명

2차원 배열과 K번의 이동 기회가 주어졌을 때, 각 이동마다 하나의 행 또는 하나의 열을 선택하여 해당 줄의 모든 원소를 반전(0→1, 1→0)시킵니다. 선택은 K번의 뒤집기가 끝난 후 각 행이 만드는 이진수의 합이 최대가 되도록 이루어져야 하며, 최종적으로 모든 행에서 만들어진 숫자들의 총합을 반환해야 합니다.

예제를 통해 문제를 자세히 살펴보겠습니다.

입력

arr[][] = {
    {1, 0, 0},
    {0, 1, 1},
    {1, 0, 1}
}
K = 2

출력

19

설명

두 번의 뒤집기를 수행합니다.

첫 번째 뒤집기 — 두 번째 행의 원소들을 모두 반전하면 배열은 다음과 같이 변합니다.

{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}}

두 번째 뒤집기 — 두 번째 열의 원소들을 모두 반전하면 배열은 다음과 같습니다.

{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}}

최종적으로 각 행이 만드는 숫자는 6, 6, 7입니다.

최대 합 = 19

해결 접근 방법

이 문제를 효율적으로 풀기 위해서는 다음과 같은 핵심 아이디어가 필요합니다.

  • 첫 번째 열을 우선적으로 1로 만든다. i번째 비트에 1이 위치하면 2i만큼의 값을 기여하기 때문에, 가장 왼쪽 비트가 가장 큰 가중치를 가집니다. 따라서 합을 최대화하려면 첫 번째 열에 최대한 많은 1(set bit)이 있어야 합니다.
  • 행을 뒤집을지 열을 뒤집을지 판단한다. 첫 번째 열의 값들을 확인했을 때 0의 개수가 1의 개수보다 많다면 해당 열 전체를 뒤집고, 그렇지 않다면 첫 원소가 0인 행들을 개별적으로 뒤집는 것이 유리합니다.

이러한 판단을 효율적으로 처리하기 위해 맵(map) 자료구조를 활용할 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
    map<int, int> flipValues;
    int updateVal, MaxSum = 0;
    for (int i = 0; i < row; ++i) {
        if (mat[i][0] == 0) {
            updateVal = 0;
            for (int j = 1; j < col; ++j)
                updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
            flipValues[updateVal] = i;
        }
    }
    map<int, int>::iterator it = flipValues.begin();
    while (K > 0 && it != flipValues.end()) {
        int updateIndex = it->second ;
        for (int j = 0; j < col; ++j)
            mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
        it++;
        K--;
    }
    MaxSum = 0;
    int zeros, ones = 0;
    for (int j = 0; j < col; ++j) {
        zeros = ones = 0;
        for (int i = 0; i < row; ++i) {
            mat[i][j] == 0 ? zeros++ : ones++;
        }
        if (K > 0 && zeros > ones) {
            MaxSum += zeros * pow(2, (col - j - 1));
            K--;
        }
        else
            MaxSum += ones * pow(2, (col - j - 1));
    }
    return MaxSum;
}
int main() {
    int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
    int K = 2;
    cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
    return 0;
}

실행 결과

The Maximum score after flipping the matrix atmost K times is 19

마무리

이 문제의 핵심은 높은 자릿수(왼쪽 열)부터 1의 개수를 최대화하는 그리디(Greedy) 전략입니다. 첫 번째 열의 0과 1의 개수를 비교해 열 단위 뒤집기 여부를 결정하고, 남은 기회는 나머지 열에 적용함으로써 최대 K번의 연산으로 최적의 점수를 얻을 수 있습니다. 시간 복잡도는 행렬의 크기에 대해 O(R × C) 수준으로 효율적입니다.