[BAEKJOON] 2740번 : 행렬 곱셈

문 제

 

소 스  코 드

#include <iostream>

void Display(int **, const int&, const int&);

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);


	int N, M, K;

	// A
	std::cin >> N >> M;
	int **A{ new int*[N] };
	for (int i = 0; i < N; ++i) A[i] = new int[M];

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			std::cin >> A[i][j];
		}
	}

	//Display(A, N, M);

	// B
	std::cin >> M >> K;
	int **B{ new int*[M] };
	for (int i = 0; i < M; ++i) B[i] = new int[K];

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < K; ++j) {
			std::cin >> B[i][j];
		}
	}

	//Display(B, M, K);


	// A * B = C
	int **C{ new int*[N] };
	for (int i = 0; i < N; ++i) C[i] = new int[K];

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) { 
			C[i][j] = 0;
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {

			for (int k = 0; k < M; ++k) {
				C[i][j] += A[i][k] * B[k][j];
			}

		}
	}

	Display(C, N, K);


	// delete A
	for (int i = 0; i < N; ++i) delete[] A[i];
	delete A;

	// delete B
	for (int i = 0; i < M; ++i) delete[] B[i];
	delete B;

	// delete C
	for (int i = 0; i < N; ++i) delete[] C[i];
	delete C;

	return 0;
}

void Display(int ** arr, const int& x, const int& y) {
	for (int i = 0; i < x; ++i) {
		for (int j = 0; j < y; ++j) {
			std::cout << arr[i][j] << " ";
		}
		std::cout << '\n';
	}
	std::cout << '\n';
}

 

풀 이

 

행렬의 곱셈을 할 경우,

A : N X M

B : M X K

A * B : N X K

 

 

$$A :\begin{bmatrix}a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{bmatrix}  
\quad B : \begin{bmatrix}b_{11} & b_{12}&b_{13} \\ b_{21} & b_{22} & b_{23} \end{bmatrix}$$

 

$$A * B \; :\begin{bmatrix}a_{11}*b_{11} + a_{12} * b_{21} & a_{11}*b_{12} + a_{12} * b_{22} & a_{11}*b_{13} + a_{12} * b_{23} 
\\ a_{21}*b_{11} + a_{22} * b_{21} & a_{21}*b_{12} + a_{22} * b_{22} & a_{21}*b_{13} + a_{22} * b_{23}  
\\ a_{31}*b_{11} + a_{32} * b_{21} & a_{31}*b_{11} + a_{32} * b_{21} & a_{31}*b_{11} + a_{32} * b_{21} \end{bmatrix}  $$

 

A*B에서 볼 경우 A의 행, B의 열에서 M자리 수를 곱하고 더한다면, 원하는 결과를 얻을 수 있다.

 

 

출 력 값

 

 

문 제  출 처

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

2740번: 행렬 곱셈