C++로 모든 행의 합이 동일한 N×N 행렬 만들기

이 문제에서는 정수 N이 주어지며, 우리의 과제는 1부터 N²까지의 숫자를 N×N 크기의 2차원 행렬에 배치하되, 각 행에 있는 요소들의 합이 모두 같아지도록 만드는 것입니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력 − N = 4

출력 −

1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15

각 행 요소들의 합은 모두 34입니다.

해결 접근 방법

이 문제를 해결하려면 각 행의 총합이 동일해지도록 행렬의 각 요소를 적절히 배치해야 합니다. 이를 위해 그리디(Greedy) 접근 방식을 사용하여 한 행씩 올바른 요소를 배치함으로써 모든 행의 합을 같게 만들 수 있습니다.

구체적인 방법은 다음과 같습니다. 먼저 1부터 N²까지의 숫자를 순서대로 초기 행렬(prevMat)에 채워 넣습니다. 그다음 아래 공식을 사용하여 새로운 행렬(resultMat)을 생성합니다.

resultMat[i][j] = prevMat[j][(i+j)%n]

이 공식은 열 우선으로 채워진 초기 행렬의 값을 대각선 방향으로 재배치하는 효과가 있어, 결과적으로 각 행의 합이 균등하게 분포됩니다.

예제 코드

아래 코드는 위 해결 방법의 구현을 보여줍니다.

#include<iostream>
using namespace std;
   int main(){
   int n = 4,i,j;
   cout<<"크기가 "<<n<<"인 행렬(모든 행의 합이 동일) :\n";
   int prevMat[n][n], resultMat[n][n];
   int c = 1;
   // 초기 행렬에 1부터 n*n까지 순서대로 값 채우기
   for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++)
         prevMat[i][j] = c++;
   }
   // 공식을 적용해 새로운 행렬 생성
   for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
         resultMat[i][j] = prevMat[j][((i+j)%n)];
      }
   }
   // 결과 행렬 출력
   for (i = 0;i<n;i++) {
      for (j=0; j<n; j++) {
         cout<<resultMat[i][j]<<"\t";
      }
      cout<<endl;
   }
}

실행 결과

크기가 4인 행렬(모든 행의 합이 동일) :
1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15

위 출력에서 확인할 수 있듯이, 각 행의 합이 모두 34로 동일한 행렬이 성공적으로 생성되었습니다. 이 알고리즘의 시간 복잡도는 O(N²)이며, 두 개의 N×N 행렬을 사용하므로 공간 복잡도 역시 O(N²)입니다.