정방 행렬(정사각형 행렬) mat[row][column]이 주어졌을 때, 행과 열의 개수가 같고 그 길이가 홀수라면, 즉 행과 열의 크기가 2로 나누어 떨어지지 않는 경우, 이 행렬의 중간 행(middle row)과 중간 열(middle column)에 속한 원소들의 곱을 구하는 것이 과제입니다.
아래 그림과 같은 경우를 생각해 볼 수 있습니다.
제약 조건
- 행렬은 반드시 정방 행렬(행과 열의 개수가 같은 행렬)이어야 합니다.
- 행과 열의 길이는 반드시 홀수여야 합니다.
입력 예시 1
mat[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}출력 예시 1
중간 행의 곱 = 120 중간 열의 곱 = 80
설명
중간 행의 곱 = 4 * 5 * 6 = 120 중간 열의 곱 = 2 * 5 * 8 = 80
입력 예시 2
mat[][] = {{3, 5, 0},
{1, 2, 7},
{9, 0, 5}}출력 예시 2
중간 행의 곱 = 14 중간 열의 곱 = 0
설명
중간 행의 곱 = 1 * 2 * 7 = 14 중간 열의 곱 = 5 * 2 * 0 = 0
문제 해결 접근 방법
- 행렬 mat[][]를 입력으로 받습니다.
- 중간 행과 중간 열에 해당하는 원소들을 순회합니다.
- 중간 행의 곱과 중간 열의 곱을 각각 계산한 뒤 결과를 출력합니다.
알고리즘
시작
함수 int product(int mat[][MAX], int n)
단계 1 → rproduct = 1, cproduct = 1로 선언 및 초기화
단계 2 → i = 0부터 i < n까지 반복
rproduct = rproduct * mat[n / 2][i]
cproduct = cproduct * mat[i][n / 2]
단계 3 → "Product of middle row: rproduct" 출력
단계 4 → "Product of middle column: cproduct" 출력
함수 int main()
단계 1 → mat[][MAX]를 다음과 같이 선언 및 초기화
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
단계 2 → product(mat, MAX) 호출
종료C 언어 구현 예제
#include <stdio.h>
#define MAX 3
int product(int mat[][MAX], int n){
int rproduct = 1, cproduct = 1;
// 중간 행과 중간 열의 원소들만 확인하여 곱을 구합니다.
for (int i = 0; i < n; i++) {
rproduct *= mat[n / 2][i];
cproduct *= mat[i][n / 2];
}
// 결과 출력
printf("Product of middle row: %d\n", rproduct);
printf("Product of middle column: %d\n", cproduct);
return 0;
}
// 드라이버 코드
int main(){
int mat[][MAX] = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
product(mat, MAX);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Product of middle row: 120 Product of middle column: 80
핵심 아이디어는 간단합니다. 행렬의 크기가 홀수 n일 때 중간 인덱스는 항상 n / 2(정수 나눗셈)가 됩니다. 따라서 하나의 반복문 안에서 mat[n / 2][i]로 중간 행의 원소를, mat[i][n / 2]로 중간 열의 원소를 차례대로 곱해주면 시간 복잡도 O(n)만에 두 곱을 모두 구할 수 있습니다.