C++로 행렬의 모든 원소를 같게 만드는 최소 연산 횟수 구하기

문제 설명

정수 K와 M × N 크기의 행렬이 주어졌을 때, 행렬의 모든 원소를 동일한 값으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다. 여기서 한 번의 연산이란 행렬의 임의의 원소에 K를 더하거나 빼는 작업을 의미합니다.

예시

입력 행렬과 K 값이 다음과 같다고 가정해 보겠습니다.

행렬:
{
    {2, 4},
    {20, 40}
}
K = 2

모든 원소를 20으로 맞추려면 총 27번의 연산이 필요합니다.

Matrix[0][0]: 2 + (K × 9) = 20 → 9번 연산
Matrix[0][1]: 4 + (K × 8) = 20 → 8번 연산
Matrix[1][1]: 40 − (K × 10) = 20 → 10번 연산
합계: 9 + 8 + 0 + 10 = 27번

접근 방법

이 문제는 중앙값(median)의 성질을 활용하면 효율적으로 해결할 수 있습니다.

1. 나머지 검증: 각 원소에는 K만큼씩만 더하거나 뺄 수 있으므로, 모든 원소를 K로 나눈 나머지가 반드시 서로 같아야 합니다. 하나라도 다르면 어떤 방법을 써도 원소들을 같은 값으로 만들 수 없으므로 -1을 반환합니다.
2. 정렬 후 중앙값 계산: 행렬의 모든 원소를 1차원 배열로 펼쳐 오름차순으로 정렬한 뒤, 중앙값을 찾습니다.
3. 중앙값으로 통일: 절댓값 기준 거리의 총합을 최소화하는 지점이 바로 중앙값이므로, 모든 원소를 중앙값으로 맞출 때 필요한 연산 횟수가 곧 최솟값이 됩니다.

원소 개수가 짝수일 경우 두 개의 가운데 값(왼쪽 중앙값과 오른쪽 중앙값) 각각에 대해 연산 횟수를 계산해 더 작은 값을 선택하는 것이 안전합니다.

C++ 구현

#include <bits/stdc++.h>
using namespace std;

int getMinOperations(int n, int m, int k, vector<vector<int>> &matrix) {
    vector<int> arr(n * m);
    int mod = matrix[0][0] % k;

   &;// 모든 원소를 K로 나눈 나머지가 같은지 확인
   &;for (int i = 0; i < n; ++i) {
       &;for (int j = 0; j < m; ++j) {
           &;arr[i * m + j] = matrix[i][j];
           &;if (matrix[i][j] % k != mod) {
               &;return -1;
           &;}
       &;}
   &;}

   &;// 정렬 후 중앙값 기준으로 연산 횟수 계산
   &;sort(arr.begin(), arr.end());
   &;int median = arr[(n * m) / 2];
   &;int minOperations = 0;
   &;for (int i = 0; i < n * m; ++i)
       &;minOperations += abs(arr[i] - median) / k;

   &;// 원소 개수가 짝수인 경우 왼쪽 중앙값도 함께 검사
   &;if ((n * m) % 2 == 0) {
       &;int newMedian = arr[(n * m) / 2 - 1];
       &;int newMinOperations = 0;
       &;for (int i = 0; i < n * m; ++i)
           &;newMinOperations += abs(arr[i] - newMedian) / k;
       &;minOperations = min(minOperations, newMinOperations);
   &;}
   &;return minOperations;
}

int main() {
   &;vector<vector<int>> matrix = {
       &;{2, 4},
       &;{20, 40},
   &;};
   &;int n = matrix.size();
   &;int m = matrix[0].size();
   &;int k = 2;
   &;cout << "Minimum required operations = "
         << getMinOperations(n, m, k, matrix) << endl;
   &;return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required operations = 27

복잡도 분석

• 시간 복잡도: 정렬이 지배적인 단계이므로 O(NM log NM)입니다.
• 공간 복잡도: 행렬의 모든 원소를 저장하기 위한 1차원 배열이 필요하므로 O(NM)입니다.