[Baekjoon] 2740번 : 행렬 곱셈

1. 문제

https://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

2. 핵심 아이디어

• N * M 행렬과 M * K 행렬이 만나 N * K 행렬이 됨

3. Python 문제풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr1 = []
for _ in range(n):
  arr1.append(list(map(int, input().split())))

m, p = map(int, input().split())
arr2 = []
for _ in range(m):
  arr2.append(list(map(int, input().split())))

q = [[0 for _ in range(p)] for _ in range(n)]

for i in range(n):
  for j in range(p):
    for k in range(m):
      q[i][j] += arr1[i][k] * arr2[k][j]

for i in q :
  for j in i :
    print(j, end = ' ')
  print()

4. Java 문제풀이