[C] 백준 2740번 행렬 곱셈

김진웅·2023년 11월 19일

2740 2740번 C c언어 백준 행렬 곱

baekjoon-study

목록 보기

31/59

링크
https://www.acmicpc.net/problem/2740

문제

NM크기의 행렬 A와 MK크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

예제 입력 1

예제 출력 1

-1 -2 6
-3 -6 12
-5 -10 18

아이디어 스케치

위 문제는 행렬의 곱 연산을 구현하는 문제이다.
행렬의 곱 연산은 위 사진과 같다. 결과 행렬의 크기는 (첫번째 행렬의 행 크기) x (두 번째 행렬의 열 크기)와 같다.

코드 분할 설명

	int N, M, K;
	int mat1[100][100];		// 첫번째 입력 행렬
	int mat2[100][100];		// 두번째 입력 행렬
	int result[100][100] = { 0, };		// 결과값을 저장할 배열

	scanf("%d %d", &N, &M);		// 첫번째 행렬의 N과 M을 입력 받음
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%d", &mat1[i][j]);
	}

	scanf("%d %d", &M, &K);		// 두번째 행렬의 M과 N을 입력 받음
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++)
			scanf("%d", &mat2[i][j]);
	}

N,M,K는 각각 100이 최댓값이므로 100x100크기의 2차원 배열로 선언
첫 번째 행렬의 값들과 두 번째 행렬의 값들을 입력받음

for (int i = 0; i < N; i++) {
		for (int k = 0; k < K; k++) {
			for (int j = 0; j < M; j++) {
				result[i][k] += mat1[i][j] * mat2[j][k];		
			}
		}
	}

이 문제의 핵심 코드이다.
위에서 살펴본 행렬의 곱 연산에 이 문제를 대입해보면 mat1[0][0] x mat2[0][0] + mat1[0][1] x mat2[1][0]이 result 행렬의 (0,0) 인덱스의 값이 된다.
result[0][1] = mat1[0][0] x mat2[0][1] + mat1[0][1] x mat2[1][1]
result[0][2] = mat1[0][0] x mat2[0][2] + mat1[0][1] x mat2[1][2]
result[1][0] = mat1[1][0] x mat2[0][0] + mat1[1][1] x mat2[1][0]
result[1][1] = mat1[1][0] x mat2[0][1] + mat1[1][1] x mat2[1][1]
result[1][2] = mat1[1][0] x mat2[0][2] + mat1[1][1] x mat2[1][2]
위 전개식을 살펴보면 한가지 규칙을 얻을 수 있다.
rseult의 각각의 인덱스는 i와 k, mat1의 인덱스는 i와 j, mat2의 인덱스는 j,k라는 것을 알 수 있다. 방금 구한 규칙을 이용하여 위 식을 일반화 해보면, result[i][k] = mat1[i][j] x mat2[j][k] + mat1[i][j] x mat2[j][k] 이 결과가 나온다.
이때 i는 mat1의 행 인덱스 이므로 N-1을 최댓값으로 가지고, j는 mat1의 열 인덱스 이므로 M-1을 최댓값으로 가진다. k는 mat2의 열 인덱스 이므로 K-1을 최댓값으로 가진다.

전체 코드

#include <stdio.h>

int main()
{
	int N, M, K;
	int mat1[100][100];		// 첫번째 입력 행렬
	int mat2[100][100];		// 두번째 입력 행렬
	int result[100][100] = { 0, };		// 결과값을 저장할 배열

	scanf("%d %d", &N, &M);		// 첫번째 행렬의 N과 M을 입력 받음
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			scanf("%d", &mat1[i][j]);
	}

	scanf("%d %d", &M, &K);		// 두번째 행렬의 M과 N을 입력 받음
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++)
			scanf("%d", &mat2[i][j]);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < K; k++) {
			for (int j = 0; j < M; j++) {
				result[i][k] += mat1[i][j] * mat2[j][k];		
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			printf("%d ", result[i][j]);		// 결과 출력
		}
		printf("\n");
	}

	return 0;

}