백준 알고리즘 19단계 분할 정복 - 행렬 곱셈 (2740) Java

1. 문제 확인

 

 

2. 문제 풀이 

 

행렬곱에서는 첫 번째 행렬의 열과 두 번째 행렬(B)의 행(M)이 일치해야 한다.

그리고 N * M 와 M * K의 행렬 곱의 결과는 크기 N * K인 행렬이 된다.

 

행렬 곱셈 점화식 C[i][j] += A[i][k] * B[k][j]

 

3*2인 행렬 A와 2*4인 행렬 B를 예로 들어본다면.
AXB인 행렬 C는 3*4인 행렬이 될 것이다.

 

그래서 이걸로 알고리즘을 짜면,

 

1. A의 1행 1열에 담긴 값을 B의 1행 1열에 담긴 값들과 곱한다. (1번 수행) [for문 1번 수행]

2. A의 1행 {2열, 3열, 4열}도 B의 1행 {2열, 3열, 4열}과 곱하므로, 1번의 과정을 4번 반복한다. [for문 1번 수행]

3. 2번의 과정을 2행에도 진행해야하므로, 총 2번 반복한다. [for문 1번 수행]

 

 

 

3. 결과