[알고리즘-자바] 백준 2740번 행렬 곱셈

본 글은 다크모드에 최적화되어 있습니다.

문제

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

2740번: 행렬 곱셈

언어

자바 Java

해설

선형대수학에서 배우는 행렬을 코드로 작성하면 되는 문제입니다.

 

 

위의 행렬을 계산하면 1행 결과로 [-1, -2, 6]이라는 결과를 얻게 됩니다. -1은 (1 * -1) + (2 * 0), -2는 (1 * -2) + (2 * 0), 그리고 6은 (1 * 0) + (2 * 3)을 통해 얻게 됩니다. 여기서 알 수 있는 점은 왼쪽 행렬은 2차원 index만 변경되고, 오른쪽 행렬은 1차원 index만 변경하며 곱하고 있음을 알 수 있습니다. 이를 다음과 같이 코드로 작성할 수  있습니다.

static int getMultiply(int[] arr1, int[][] arr2, int w) {
    int sum = 0;
    for (int i = 0; i < arr1.length; i++) {
        sum += arr1[i] * arr2[i][w];
    }
    return sum;
}

 

배열 arr1은 행만 담고 있는 배열([1,2])이고, 배열 arr2는 곱의 대상인 행렬을 의미합니다. 이때, w는 행렬 (n x m)(m x k)에서 공통되는 m을 의미합니다. sum을 계산하는 과정을 보면, arr1은 열의 위치만 변경하고 있고, arr2는 열을 고정한 채 행의 위치만 변경하며 계산하고 있습니다. 이는 사진에서 보았듯이, 왼쪽 행렬은 열만 변경되고, 오른쪽 행렬은 행만 변경하며 계산하는 과정이라고 볼 수 있습니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] arr1 = new int[n][m];
        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++)
                arr1[i][j] = Integer.parseInt(input[j]);
        }

        input = br.readLine().split(" ");
        int k = Integer.parseInt(input[1]);
        int[][] arr2 = new int[m][k];
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < k; j++)
                arr2[i][j] = Integer.parseInt(input[j]);
        }


        for (int i = 0; i < n; i++) {
            for (int w = 0; w < k; w++)
                sb.append(getMultiply(arr1[i], arr2, w) + " ");

            sb.append("\n");
        }

        System.out.println(sb);
    }

    static int getMultiply(int[] arr1, int[][] arr2, int w) {
        int sum = 0;
        for (int i = 0; i < arr1.length; i++) {
            sum += arr1[i] * arr2[i][w];
        }
        return sum;
    }
}