[백준_2740번] 행렬 곱셈

https://www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_2740 {
	public static int a[][],b[][],result[][];
	public static int n,m,k;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		// n X m 크기 a행렬 
		n=sc.nextInt();
		m=sc.nextInt();
		a=new int[n][m];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				a[i][j]=sc.nextInt();

		// m X k 크기 b행렬
		m=sc.nextInt();
		k=sc.nextInt();
		b=new int[m][k];
		
		for(int i=0;i<m;i++)
			for(int j=0;j<k;j++)
				b[i][j]=sc.nextInt();
		
		// 결과를 저장할 행렬의 크기는 n X k
		result=new int[n][k];
		// 행렬 계산	
		for(int i=0;i<n;i++) { // i : a행렬의 row
			for(int j=0;j<k;j++) { // j : b행렬의 col
				
				// a행렬의 row와 b행렬의 col의 각 값들을 곱한 뒤 더한다.
				for(int k=0;k<m;k++) { // 더해주는 원소의 개수는 k개
					
					/* A행렬의 i번째 row의 k번째 열 원소와, B
					 * 의 j번째 col의 k번째 행 원소를 곱한 뒤 누적합을 결과 행렬의 저장
					 */
					result[i][j]+=a[i][k]*b[k][j];
				}
			}
		}
		
		// 결과 행렬 출력
		for(int i=0;i<n;i++) {
			for(int j=0;j<k;j++)
				System.out.print(result[i][j]+" ");
			System.out.println();
		}
	}
}

[고찰]

 이번 문제는 기본적인 행렬 계산만 할 수 있다면 풀 수 있는 문제였다. 하지만 분할 정복 카테고리에 있는 문제였기 때문에 어떻게 분할 정복으로 풀 수 있을까 궁금했다. 이러한 부분은 다른 사람의 포스팅을 보면 이해하려 했지만 내용이 복잡하고 어려워 아직 공부가 더 필요할 것 같다.