C++로 풀어보는 0과 n으로만 이루어진 3×3 행렬의 최대 행렬식 문제

문제 개요

양의 정수 n이 하나 주어집니다. 우리가 찾아야 할 것은 각 원소가 0 또는 n으로만 구성된 3×3 행렬 중에서 행렬식(determinant)이 가장 커지는 행렬입니다.

핵심 아이디어

결론부터 말하면, 원소가 0 또는 n뿐인 3×3 행렬이 가질 수 있는 행렬식의 최댓값은 항상 다음과 같습니다.

최대 행렬식 = 2 × n³

그 이유는 간단합니다. 각 행에서 공통 인수 n을 묶어내면, 남는 것은 0과 1로만 이루어진 3×3 행렬의 행렬식에 n³을 곱한 형태가 됩니다. 그리고 3×3 크기의 0-1 행렬이 가질 수 있는 행렬식의 절댓값 최댓값은 2로 알려져 있으므로, 전체 행렬식의 최댓값은 2 × n³이 됩니다.

예시

n = 15일 때, 다음과 같은 행렬을 만들 수 있습니다.

{{15, 15, 0}, {0, 15, 15}, {15, 0, 15}}

이 행렬의 행렬식을 계산하면 다음과 같습니다.

2 × (15)³ = 6750

이 값이 해당 조건에서 도달할 수 있는 최댓값입니다.

C++ 구현

아래 코드는 주어진 n에 대해 최적의 행렬을 화면에 출력하고, 최대 행렬식 값을 함께 계산해 보여줍니다.

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

// 최대 행렬식은 항상 2 * n^3
int getMaxDeterminant(int n){
    return (2 * n * n * n);
}

// 최적 행렬 출력
void printMatrix(int n){
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if ((i == 0 && j == 2) ||
                (i == 1 && j == 0) ||
                (i == 2 && j == 1)) {
                printf("%-5d", 0);
            } else {
                printf("%-5d", n);
            }
        }
        printf("\n");
    }
}

int main() {
    int n = 15;
    cout << "행렬:\n";
    printMatrix(n);
    cout << "\n최대 행렬식 = " << getMaxDeterminant(n) << endl;
    return 0;
}

실행 결과

행렬:
15   15   0
0    15   15
15   0    15

최대 행렬식 = 6750

정리

이 문제의 요점은 복잡한 탐색 없이도 수학적 성질을 이용해 답을 바로 도출할 수 있다는 점입니다. 0과 n으로만 채워진 3×3 행렬의 최대 행렬식은 언제나 2 × n³이며, 위 코드처럼 대각선 방향으로 0을 세 개 배치한 순환(circulant) 형태의 행렬이 그 최댓값을 실현합니다. 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)로 매우 효율적입니다.