문제
N x M 행렬 A와 M x K 행렬 B가 주어질 때, 두 행렬의 곱 A x B를 구하라.
입력
첫째 줄에 N, M, 다음 N줄에 행렬 A, 다음 줄에 M, K, 다음 M줄에 행렬 B가 주어진다. N, M, K는 모두 100 이하이고 원소는 절댓값 100 이하 정수이다.
출력
N x K 행렬 A x B를 N줄에 걸쳐 출력한다. 각 원소는 공백으로 구분한다.
예제
| 입력 | 출력 |
|---|---|
3 2 1 2 3 4 5 6 2 3 1 2 3 4 5 6 | 9 12 15 19 26 33 29 40 51 |
풀이
행렬 곱셈의 정의를 그대로 구현한다. 결과 행렬 C의 (i, j) 원소는 A의 i행과 B의 j열의 내적이다.
- N x M 행렬 A와 M x K 행렬 B를 입력받는다
- 3중 루프로 결과 행렬의 각 원소를 계산한다: C[i][j] = sum(A[i][k] * B[k][j]) (k: 0~M-1)
- 결과를 공백으로 구분하여 출력한다
핵심 아이디어: 행렬 곱셈의 정의를 그대로 3중 루프로 구현하며, N, M, K 모두 100 이하이므로 O(NMK)로 충분하다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day139BOJ2740행렬곱셈 { // 2740 행렬 곱셈
static int N, M, K;
static int[][] A, B;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++)
A[i][j] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
B = new int[M][K];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < K; j++)
B[i][j] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
int sum = 0;
for (int k = 0; k < M; k++)
sum += A[i][k] * B[k][j];
sb.append(sum).append(' ');
}
sb.append('\n');
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N * M * K)
- 공간: O(N * K + N * M + M * K)