/ BOJ

BOJ_2740_행렬곱셈_JAVA

문제 : 행렬곱셈

링크 : BOJ_2740_행렬곱셈

접근 방식

행렬의 곱셈에 대한 문제이다. 이 문제도 분할 정복 카테고리에 묶여있었기 때문에 분할정복으로 풀어보려고 했으나, 방법이 생각이 나지 않았다. 결국 일반적인 행렬의 곱셈의 방식을 이용해 값을 구해주었다.

풀이 방법

  1. 행렬의 크기를 읽어들여 각각 2개의 배열로 생성하여 값을 저장한다.

  2. NxM과 MxK 배열이 있다면 NxK 크기의 배열을 생성한다.

  3. 생성한 배열에 값을 집어넣는데 그 값은 M크기만큼 반복하여 누적시킨 각 행렬의 행과 열의 값을 곱한 값이다. 고등학교때 배운 그 행렬의 곱셈이다.

  4. 값을 모두 할당한 배열을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2740_행렬곱셈 {
	static int N,M,K, A[][], B[][];
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.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(in.readLine()," ");
			for(int j=0;j<M;j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st= new StringTokenizer(in.readLine()," ");
		st.nextToken();
		K = Integer.parseInt(st.nextToken());

		B = new int[M][K];
		for(int i=0;i<M;i++) {
			st= new StringTokenizer(in.readLine()," ");
			for(int j=0;j<K;j++) {
				B[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int[][] C = new int[N][K];

		for(int i=0;i<N;i++) {
			for(int j=0;j<K;j++) {

				for(int k=0;k<M;k++) {
					C[i][j] += A[i][k] * B[k][j];
				}
				System.out.print(C[i][j]+" ");
			}
			System.out.println();
		}

	}

}