이 문제에서는 부울 값(즉, 0과 1)과 정수 K로 구성된 2차원 배열 arr[]이 주어집니다. 우리의 임무는 이진 행렬을 최대 K번 뒤집은 후 최대 점수를 찾는 프로그램을 만드는 것입니다. C++.
문제 설명 − 여기에서 2차원 배열에 대해 k가 이동하려면 배열의 요소에 의해 생성되는 숫자를 찾아야 합니다. 각 이동에서 행이나 열을 가져와 행이나 열의 모든 요소를 뒤집습니다. 행렬의 행에서 K번 뒤집힌 후 생성된 수를 최대화해야 한다는 점을 염두에 두고 선택을 할 것입니다. 그리고 행에 생성된 모든 숫자의 합계를 반환해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[][] = {
{1, 0, 0},
{0, 1, 1},
{1, 0, 1}
}
K = 2 출력
19
설명
2개의 플립이 있습니다.
첫 번째 뒤집기 - 두 번째 행 요소를 뒤집습니다. 이렇게 하면 배열이 만들어집니다.
{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}} 두 번째 뒤집기 - 두 번째 열 요소를 뒤집습니다. 이렇게 하면 배열이 만들어집니다.
{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}} 각 행에 생성된 최종 숫자는 6, 6, 7입니다.
Maximum sum = 19.
솔루션 접근 방식
문제를 해결하려면 첫 번째 열의 요소를 먼저 1로 만들어야 합니다. i번째 열의 1은 가능한 가장 큰 숫자인 2i에 기여합니다(하나의 세트 비트가 고려되는 경우). 따라서 가장 왼쪽 열은 합이 최대가 되도록 최대 1(설정 비트) 수를 가져야 합니다. 그런 다음 각 행의 다른 요소로 이동합니다.
행이나 열을 뒤집을 필요가 있는지 확인합니다. 열의 다른 값을 확인해야 합니다. 즉, 행의 모든 첫 번째 요소입니다. 0의 수가 1보다 큰 경우. 우리는 열을 뒤집을 것입니다. 그렇지 않으면 행을 뒤집습니다.
문제를 해결하기 위해 지도 데이터 구조를 사용할 것입니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#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