n × n 크기의 정방 행렬(square matrix)이 주어졌다고 가정해 보겠습니다. 이때 다음과 같은 값들을 특수 요소(special element)라고 부릅니다.
주 대각선(main diagonal)에 위치한 값
부 대각선(secondary diagonal)에 위치한 값
위쪽에 정확히 (n − 1) / 2개의 행이 있고, 아래쪽에도 같은 개수의 행이 있는 중앙 행의 값
왼쪽과 오른쪽에 정확히 (n − 1) / 2개의 열이 있는 중앙 열의 값
이 문제의 목표는 행렬에서 이러한 특수 값들을 모두 찾아 그 합을 구하는 것입니다.
예를 들어 입력이 n = 4, mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}이라면 출력 결과는 107이 됩니다.
풀이 접근 방식
이 문제는 행렬의 모든 요소를 순회하면서 해당 요소가 특수 요소 조건에 부합하는지 검사하면 됩니다. 조건은 다음 네 가지입니다.
i == j: 행 인덱스와 열 인덱스가 같으면 주 대각선 요소입니다.i + j == n - 1: 두 인덱스의 합이 n − 1이면 부 대각선 요소입니다.i == n / 2: 중앙 행에 해당합니다.j == n / 2: 중앙 열에 해당합니다.
이를 의사 코드로 표현하면 다음과 같습니다.
res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
for initialize j := 0, when j < n, update (increase j by 1), do:
if i is same as j or i is same as n / 2 or j is same as n / 2 or i + j is same as n - 1, then:
res := res + mat[i, j]
print(res)C++ 구현 예제
아래의 실제 C++ 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, vector<vector<int>> mat) {
int res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j || i == n / 2 || j == n / 2 || i + j == n - 1)
res += mat[i][j];
}
cout << res << endl;
}
int main() {
int n = 4;
vector<vector<int>> mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
solve(n, mat);
return 0;
}입력
4, {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}출력
107
결과 분석
n = 4인 위 행렬에서 특수 요소는 주 대각선의 1, 6, 11, 16 / 부 대각선의 4, 7, 10, 13 / 중앙 행(i = 2)의 9, 12 / 중앙 열(j = 2)의 3, 15입니다. 즉, 특수 요소 전체는 1, 3, 4, 6, 7, 9, 10, 11, 12, 13, 15, 16이며, 이들을 모두 더하면 107이 되어 프로그램의 출력 결과와 일치합니다.
시간 복잡도는 행렬의 모든 칸을 한 번씩 확인하므로 O(n²)이며, 별도의 추가 메모리 없이 상수 공간으로 해결할 수 있습니다.