2740번 행렬 곱셈

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

---

문제

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

입력

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

출력

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

 

예제 입력 1

3 2
1 2
3 4
5 6
2 3
-1 -2 0
0 0 3

 

예제 출력 1

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

---

<알고리즘>

1) 행과 열을 잘 지켜서 두 개의 행렬을 받는다.

2) 첫 번째 행렬을 first(N*M), 두 번째 행렬을 second(M*K)이라고 할때, 

   결과값인 행렬 result는 N*K이고, 각 칸의 값은 M번의 덧셈으로 이루어져 있다.

3) 행렬의 곱셈 법칙을 잘 이용해서 식을 만들어주면 모든 칸의 값을 손쉽게 구할 수 있다.

   (모든 칸의 덧셈과 곱셈을 적어놓고 규칙을 찾는 것이 빠름)

 

예시) 예제의 두 행렬을 곱했을 때의 결과값이 되는 행렬 

(0,0) (f(0,0)*s(0,0))+(f(1,0)*s(0,1))	(1,0) (f(0,0)*s(1,0))+(f(1,0)*s(1,1))	(2,0) (f(0,0)*s(2,0))+(f(1,0)*s(2,1))
(0,1) (f(0,1)*s(0,0))+(f(1,1)*s(0,1))	(1,1) (f(0,1)*s(1,0))+(f(1,1)*s(1,1))	(2,1) (f(0,1)*s(2,0))+(f(1,1)*s(2,1))
(0,2) (f(0,2)*s(0,0))+(f(1,2)*s(0,1))	(1,2) (f(0,2)*s(1,0))+(f(1,2)*s(1,1))	(2,2) (f(0,2)*s(2,0))+(f(1,2)*s(2,1))

 

 

 

메모리 : 2016KB    시간 : 4ms

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N = 0;
	int M = 0;
	cin >> N >> M;

	vector<vector<int>> first(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> first[i][j];
		}
	}
	
	int K = 0;
	cin >> M >> K;
	vector<vector<int>> second(M, vector<int>(K));
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++) {
			cin >> second[i][j];
		}
	}


	vector<vector<int>> result(N, vector<int>(K));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			int answer = 0;
			for (int a = 0; a < M; a++) {
				answer += first[i][a] * second[a][j];
			}
			result[i][j] = answer;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}